0%

演化多目标优化:基于支配的经典算法NSGA-II

最近在学习并尝试实现演化多目标优化的相关算法,希望我能通过这篇博客把算法了解得更加透彻orz

基础篇

帕累托支配

在多目标优化领域,一般来说,决策变量和目标都是由多个元素组成的,而不同目标之间往往难以比较。如果将决策/目标视作一个向量\(\mathbf{x}\),我们用帕累托支配(Pareto dominance)来刻画向量间的关系。对于两个\(n\)维向量\(\mathbf{x}^{(1)}, \mathbf{x}^{(2)}\),我们称\(\mathbf{x}^{(1)}\)支配\(\mathbf{x}^{(2)}\)(记作\(\mathbf{x}^{(1)} \prec \mathbf{x}^{(2)}\))当且仅当\(\forall 1 \leq i \leq n,\ \mathbf{x}^{(1)}_i \leq \mathbf{x}^{(2)}_i\),且\(\exists 1 \leq i \leq n,\ \mathbf{x}^{(1)}_i < \mathbf{x}^{(2)}_i\)

Read more »

线性代数复习:置换矩阵和“名次向量”

没事瞎水博客系列……

在日常处理矩阵的时候,有时我们希望在不更改矩阵的前提下获知其每一行/列的字典序“名次”(rank)。MATLAB/NumPy分别提供了sortrows/argsort方法来获得一个“索引向量”(index vector),表示排序后的矩阵的每一行/列对应原矩阵的行/列号。只需对索引向量再做一次排序,便可得到对应的”名次向量“(rank vector)。对应MATLAB代码大致如下:

1
2
[~, index] = sortrows(matrix);
[~, rank] = sort(index);

为了深入理解这个操作背后的原理,我参考了StackExchange上的这篇回答。从他的证明过程中我发现了一个关键:排序前后两个矩阵的关系可以用排列/置换(permutation)来刻画。下面我将站在线性代数的视角来系统化解释一下“名次向量”背后的原理。

Read more »

2021-02-04 Update: 早知道就先升级到18.04或者20.04来配置了,也不会有下面这么多坑了orz


感谢上天让我在忙的头都要掉了的时候还有时间来写这篇博客记录这艰难曲折的配环境之路……希望以下内容对读者没有任何帮助。

Read more »

算法复习笔记:网络流

龟速补上欠下的账ing……\(\DeclareMathOperator{\capa}{cap}\)

写完发现读着好晦涩,但数学不就是这样的吗🌚

基本概念/符号表示

为了方便下文叙述,现做如下规定/定义:

\(G = (V, E)\)是有向、无平行边的图,每条边边权为正,其中有一个源点(source)\(s\)汇(sink)点\(t\)满足:没有一条边以\(t\)为起点,或以\(s\)为终点。

对某边\(e \in E\),记该边边权为\(c(e)\)

Read more »

算法复习笔记:多项式凭什么能FFT?

写在前面

本文仅面向学习FFT算法的CS学生。文中关于傅里叶变换的阐述仅用于帮助快速简要地理解算法背后时域/频域变换的意义,逻辑性不会像「信号与系统」课那么强。本人没系统学过「信号与系统」这门课,能写出这篇文章也要感谢来自FDU、SCUT的两位同学的帮助。欢迎各位大佬对本文内容进行指正!

要系统学习「信号与系统」的内容,可参阅奥本海默著的《信号与系统》一书。

在我学习FFT时,第一个面对的问题背景是「给定两个多项式,如何快速求得二者的乘积?」老师或者博客会先介绍多项式的系数表示和点值表示(在下一节也会再啰嗦一遍),然后引入单位根分治思想来实现两种表示法间的转换。这篇专栏对算法内容及前置知识的讲解算是非常详尽的了,但它并没有解决一个问题:傅里叶变换的本质是将时域上的卷积转化成频域上的乘法,那么多项式的系数/点值表示为什么能和信号的时域/频域对应?本文将从偏向EE的角度来探讨这个算法,并尝试揭示其中的关联。

Read more »

算法复习笔记:贪心求最优Caching策略

题目来自Algorithm design / Jon Kleinberg, Eva Tardos.—1st ed. 的4.3节。

参考文章:http://notebook.xyli.me/CS161/Intro-to-greedy-algo1/

问题背景

假设现在有一个容量为\(k\)的缓存(cache)空间,和\(m\)个内存block访问请求\(d_1, d_2, \dots, d_m\)。对于第\(i\)个请求\(d_i\),如果请求的block在缓存中,称其为一次命中(hit),否则称其为一次失效/缺页(miss)。若出现miss,则需要从内存中读取该block并写入缓存(若缓存已满则会替换掉其中一个block)。现给定请求序列,求一个最优缓存(caching)策略使得miss尽可能少。

Read more »

码农的自我修养——插头DP

想不到促使我学习插头DP的动机竟然是一道算法课的Lab题,还被网上的假教程演了半天……姑且把学到的东西写一写,纪念一下我对着一屏幕的表画了大半天图的自闭时光。

起这个标题的原因实在一篇博客里看到“转移过程十分码农”,敲完代码深以为然,就借用过来了。

以下内容仅为插头DP的一种应用情形。若要应用于其他题目,需要对过程略作修改。

前置知识:状态压缩DP、BFS、哈希

Read more »

定义

一个整数\(x\)对另一个整数\(p\)二次剩余,指\(x^2\)\(p\)的余数。

我们称整数\(d\)\(p\)的二次剩余当且仅当\(\exists x \in \mathbb{Z} \mbox{ s.t. } x^2 \equiv d \pmod p\);反之,称\(d\)\(p\)的非二次剩余

上下文无歧义的情况下可以简称为剩余非剩余

Read more »

置换

置换\([\![1, n]\!] \triangleq \{1, 2, \dots, n\}\)到自身的1-1变换:\([\![1, n]\!] \rightarrow [\![1, n]\!]\)

\(p: i \rightarrow a_i, (a_i \neq a_j, i \neq j)\)

其中\(a_1, a_2, \dots, a_n\)\([\![1, n]\!]\)的一个全排列

称此置换为\(n\)阶置换,记为:

\(p=\pmatrix{1&2&\cdots&n\\a_1&a_2&\cdots&a_n}\)

\(n\)阶置换共有\(n!\)个。

Read more »

这篇文章应该是会长期更新的吧……大概

是不是颜色调的很淡你们就看不到我

去年11月份,怀揣着即将成为CS系学生的觉悟,我决定像周围大佬们一样建立一个属于自己的博客。可气的是,我电脑上的WSL运行的是Ubuntu 16.04.6 LTS,而Ubuntu自己的apt向来不会安装最新版本(或者较新版本)的工具(当然也不排除我懒得搞镜像源的问题),在经历了配置Nginx失败、npm下载等一年之类的问题之后,我放弃了WordPress和Hexo,并在pg999w的推荐下入坑了Hugo。However,我的Hugo源文件一开始是在嫖来的t123yh的服务器上编辑的,这也带来了一系列问题比如无法本地预览、服务器重置以后必须重新配置而我又没有写文章来记录、以及本人很懒根本就没更新文章。总而言之,作为一个已经进入CS系的韭菜,我决定回到Hexo坑并让这个博客复活。在此感谢WhexyEveneko的帮助。

前排提醒:下列操作均在WSL环境下进行。必要时需sudo

Read more »