多目标遗传算法程序
排课问题的本质是将课程、教师和学生在合适的时间段内分配到合适的教室中，涉及到的因素较多，是一个多目标的调度问题，在运筹学中被称为时间表问题（Timetable Problem，TTP）。设一个星期有n个时段可排课，有m位教师需要参与排课，平均每位教师一个星期上k节课，在不考虑其他限制的情况下，能够推出的可能组合就有 种，如此高的复杂度是目前计算机所无法承受的。因此众多研究者提出了多种其他排课算法，如模拟退火，列表寻优搜索和约束满意等。
Github ： https://github.com/xiaochus/GeneticClassSchele
遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法的流程如下所示：
遗传算法首先针对待解决问题随机生成一组解，我们称之为种群（Population）。种群中的每个个体都是问题的解，在优化的过程中，算法会计算整个种群的成本函数，从而得到一个与种群相关的适应度的序列。如下图所示：
为了得到新的下一代种群，首先根据适应度对种群进行排序，从中挑选出最优的几个个体加入下一代种群，这一个过程也被称为精英选拔。新种群余下的部分通过对选拔出来的精英个体进行修改得到。
对种群进行修改的方法参考了生物DAN进化的方法，一般使用两种方法： 变异 和 交叉 。 变异 的做法是对种群做一个微小的、随机的改变。如果解的编码方式是二进制，那么就随机选取一个位置进行0和1的互相突变；如果解的编码方式是十进制，那么就随机选取一个位置进行随机加减。 交叉 的做法是随机从最优种群中选取两个个体，以某个位置为交叉点合成一个新的个体。
经过突变和交叉后我们得到新的种群（大小与上一代种群一致），对新种群重复重复上述过程，直到达到迭代次数（失败）或者解的适应性达到我们的要求（成功），GA算法就结束了。
算法实现
首先定义一个课程类，这个类包含了课程、班级、教师、教室、星期、时间几个属性，其中前三个是我们自定义的，后面三个是需要算法来优化的。
接下来定义cost函数，这个函数用来计算课表种群的冲突。当被测试课表冲突为0的时候，这个课表就是个符合规定的课表。冲突检测遵循下面几条规则：
使用遗传算法进行优化的过程如下，与上一节的流程图过程相同。
init_population ：随机初始化不同的种群。
mutate ：变异操作，随机对 Schele 对象中的某个可改变属性在允许范围内进行随机加减。
crossover ：交叉操作，随机对两个对象交换不同位置的属性。
evolution ：启动GA算法进行优化。
实验结果
下面定义了3个班，6种课程、教师和3个教室来对排课效果进行测试。
优化结果如下，迭代到第68次时，课程安排不存在任何冲突。
选择1203班的课表进行可视化，如下所示，算法合理的安排了对应的课程。
2. MATLAB遗传算法工具箱求解非线性多目标优化问题
将下属两个目标函数分别保存在两个m文件中
function f1=func1(x) %第一目标函数
f1=x(:,1).*x(:,1)./4+x(:,2).*x(:,2)./4;
function f2=func2(x) %第二目标函数
f2=x(:,1).*(1-x(:,2))+10;
function GA()
clear;clc;close all
NIND=100; %个体数目
MAXGEN=50; %最大遗传代数
NVAR=2; %变量个数
PRECI=20; %变量的二进制位数
GGAP=0.9; %代沟
trace1=[];trace2=[];trace3=[]; %性能跟踪
%建立区域描述器
% rep([PRECI],[1,NVAR])
FieldD=[rep([PRECI],[1,NVAR]);rep([1;2],[1,NVAR]);rep([1;0;1;1],[1,NVAR])];
Chrom=crtbp(NIND,NVAR*PRECI); %初始种群
v=bs2rv(Chrom,FieldD) ; %初始种群十进制转换
gen=1;
while gen<MAXGEN,
[NIND,N]=size(Chrom);
M=fix(NIND/2);
ObjV1=func1(v(1:M,:)); %分组后第一目标函数值
FitnV1=ranking(ObjV1); %分配适应度值
SelCh1=select('sus',Chrom(1:M,:),FitnV1,GGAP); %选择
ObjV2=func2(v(M+1:NIND,:)); %分组后第二目标函数值
FitnV2=ranking(ObjV2); %分配适应度值
SelCh2=select('sus',Chrom(M+1:NIND,:),FitnV2,GGAP); %选择
SelCh=[SelCh1;SelCh2]; %合并
SelCh=recombin('xovsp',SelCh,0.7); %重组
Chrom=mut(SelCh); %变异
v=bs2rv(Chrom,FieldD);
trace1(gen,1)=min(func1(v));
trace1(gen,2)=sum(func1(v))/length(func1(v));
trace2(gen,1)=min(func2(v));
trace2(gen,2)=sum(func2(v))/length(func2(v));
trace3(gen,1)=min(func1(v)+func2(v));
trace3(gen,2)=sum(func1(v))/length(func1(v))+sum(func2(v))/length(func2(v));
gen=gen+1;
end
figure(1);clf;
plot(trace1(:,1));hold on;plot(trace1(:,2),'-.');
plot(trace1(:,1),'.');plot(trace1(:,2),'.');grid on;
legend('解的变化','种群均值的变化')
xlabel('迭代次数');ylabel('目标函数值');
figure(2);clf;
plot(trace2(:,1));hold on;
plot(trace2(:,2),'-.');
plot(trace2(:,1),'.');
plot(trace2(:,2),'.');grid;
legend('解的变化','种群均值的变化');
xlabel('迭代次数');ylabel('目标函数值');
figure(3);clf;
plot(trace3(:,1));hold on;
plot(trace3(:,2),'-.');
plot(trace3(:,1),'.');
plot(trace3(:,2),'.');grid;
legend('解的变化','种群均值的变化');
xlabel('迭代次数');ylabel('目标函数值');
figure(4);clf;plot(func1(v));hold on;
plot(func2(v),'r-.');grid;
3. 多目标优化问题
形式化定义：
特点：
①包含多个可能有冲突的目标函数。
②希望找到能够很好平衡全部优化目标的解集；
帕累托最优是指资源分配的一种理想状态。给定固有的一群人和可分配的资源，如果从一种分配状态到另一种分配状态，在没有使得任何人的境况变坏的前提下，使得至少有一个人变得更好，这就是帕累托改善的状态；换言之，不可能在不是任何其他人受损的情况下再改善某些人的境况。
支配（Dominace） ：当x1和x2满足如下条件时称x1支配x2：①对于所有目标函数x1不比x2差；②至少在一个目标函数上，x1严格比x2要好。
对于点1和点2：对于目标函数f1是越大越好，在取相同f2时，点1比点2好；对于目标函数f2是越小越好，在取相同f1时，点1比点2好。所以点1支配点2。
对于点1和点4：目标函数f1上，取相同f2时，点4比点1好；目标函数f2上，取相同f1时，点1比点4好。所以点1和点4互不支配。
不可支配解集（Non-dominated solution set） ：当一个解集中任何一个解都不能被该集合中其他解支配，那么就称该解集为不可支配解集。
帕累托最优解集（Pareto-optimal set ）：所有可行中的不可支配解集被称为帕累托最优解集。
帕累托最优前沿面（Pareto-optimal front） ：帕累托最优解集的边界（boundary）被称为帕累托最优前沿面。
多目标优化问题的目标 ：①寻找尽可能接近最优的解集；②尽可能增大找到解的多样性。
优点：简单
缺点：①很难设定一个权重向量能够获得帕累托最优解；②在一些非凸情况下不能够保证获得帕累托最优解。
优点：能够应用到凸函数和非凸函数场景下。
缺点：函数需要精心选择，需要在独立函数的最小值或最大值之内。
优点：weighted Techebycheff metirc能够保证获得所有帕累托最优解。
缺点：①需要有每个函数最大值和最小值的先验知识；②需要每个目标函数的z*能够独立被找到；③对于较小的p值，不一定保证所有能够获得所有的帕累托最优解；④随着p增加，问题会变得不可求导。
①随机产生初始种群；
②计算各点的目标函数值和约束函数值；
③根据目标函数值对种群分级；
④根据约束函数值和分级结果计算各点的约束罚项、劣解罚项及总罚项；
⑤根据各点的总罚项计算适应度；
⑥根据各点的适应度，进行选择、交叉和变异操作，生成新种群；
⑦将总罚项为0的点放入非劣解集候选表，对候选表进行检查，保留第1级非劣点，删除其他点；
⑧检查是否收敛，如没有，转到步骤②；
⑨删除候选表中与其他店距离太近的点；
⑩输出候选表中的帕累托最优解集及对应的目标函数值；
最后，决策人根据个人偏好从帕累托最优解集中挑选出最适合该问题的解。
遗传算法相比传统的算法的优点是能够得到一个最优解集，而不是单单一个最优解，这样会提供更多的选择，但是计算的复杂度可能稍高，而且里面涉及的一些函数需要精心设计。
1.权重系数转换法
对每个目标函数fi(x)赋予权重wi，wi为目标函数的重要程度。μ=Σwi·fi(x)，这里就将多目标转化为单目标函数，将μ作为评价函数。
2.并列选择法
主要步骤：(1)将种群按照目标函数个数等分为子种群，为每个子种群分配一个目标函数。(2)将子种群中的个体按照各自的目标函数选择出适应度高的个体，然后将其组成一个子种群。(3)再将子种群进行交配、变异、生成下一代父亲种群。然后再重复第一步。
并列选择法的缺点在于易于生成单个目标函数的极端最优解，而较难生成一种多个目标在某种程度上都比较满意的折中解。
3.排序选择法
基本思想就是基于“帕累托最优个体”的概念对群体中的个体进行排序，然后根据这个次序进行种群选择。这样的话，就能够让帕累托最优个体有更多的机会遗传到下一代。这种方法的缺点是仅仅度量了各个个体之间的优越次序，而并未度量各个个体的分散程度，所以容易生成相似的解，而不是分布较广的多个最优解。
4.共享函数法
针对排序选择方法的缺点，即所求的几个最优解通常都是集中于最优解集合的某一个小区域内，而不是分散在整个帕累托最优解集合。由此，引出了基于共享函数的 小生境技术 （小生境技术就是将每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个群，再在种群中，以及不同种群中之间，杂交，变异产生新一代个体群。同时采用预选择机制和排挤机制或分享机制完成任务。）。该算法对相同个体或类似个体的数目加以限制，以便能够产生出种类较多的不同的最优解。这就引出一个问题，怎么衡量两个个体之间的相似度？这就是小生境数。顾名思义，小生境就是在一个小环境中相似的个体种群。最常见的公式为：
s(d)为共享函数，是表示群体中两个个体之间密切关系程度的一个函数。d(X,Y)为个体X,Y之间的hanmin距离，也是用于衡量个体间相似度的一个函数。在计算出小生境数后，可以是小生境数较小的个体能够有更多的机会被选中，遗传到下一代群体中，即相似程度较小的个体能够有更多的机会被遗传到下一代群体中。
缺点：每次选择操作时都需要进行大量的个体之间的优越关系的评价和比较运算，使得算法搜索效率较低。
5.Horn和Nafploitis印的基于小生境帕累托多目标遗传算法(NPGA)
类似于第2个的并列选择法，将每一代个体划分为若干类，每个类别选出若干适应度较大的个体作为一个类的优秀代表组成一个种群，然后交配变异产生新一代种群。基于这种小生境的遗传算法（Niched Genetic Algorithms，NGA），可以更好地保持解的多样性，同时具有很高的全局寻优能力和收敛速度，特别适合于复杂多峰函数的优化问题。
6.Srinvivas和Deb的非支配排序遗传算法NSGA
1980年提出来的，在遗传算法的基础上对选择再生方法进行改进：将每个个体按照他们的支配和非支配关系进行再分层，再做选择操作，从而达到目的。
其分层的含义就是取出种群中的非支配个体组成一个小种群（第一个非支配最优层），并赋予其中所有个体一个共享的虚拟适应度值。然后再取出个体后的种群中继续取出非支配个体，再将它们组成一个小种群（第二个非支配最优层），并且赋予所有个体一个共享的虚拟适应度值。重复上述步骤，直到原始种群分配完毕，这就是分层，也叫非支配型排序。
非支配型排序遗传算法的缺点：①计算复杂度较高；②没有精英策略；③需要制定共享半径。
针对以上问题，k·Deb 于2002年提出了 7 的方法。
7.带精英策略的非支配排序遗传散发——NSGAII
1).采用快速非支配型排序，降低了算法复杂度。其复杂度降为了O(MN**2)。
2).提出了拥挤度和拥挤度比较算子，代替需要指定共享半径的适应度共享策略。并在快速排序后的同级比较中作为胜出标准。使准pareto解中的个体能扩展到整个pareto域中，并均匀分布，保持了种群的多样性。
3).引入精英策略，扩大采样空间。将父代种群和子代种群合并，保证优良个体能够留存下来。
其算法步骤如下：1.首先随机产生数量为n的初始种群，然后对其进行非支配型排序。接下来，就是常规的选择，交叉，变异操作产生第一代子代种群。2.然后，从第二代开始，将父代和子代合并。然后对其进行快速非支配型排序，同时计算每个非支配层的个体进行拥挤度的计算。然后根据非支配关系和拥挤度来选择合适的个体组成新的父代种群。最后通过再通过选择，交叉，变异产生子代。3.接下来，重复第二步。
具体做法参考：https://blog.csdn.net/quinn1994/article/details/80679528/
4. 怎么评价MATLAB中gamultiobj函数（多目标遗传算法）的计算结果比如下面的函数和其部分结果
您好，多目标遗传算法可以得到Pareto Front图，即您展示的结果。至于评价方法应由您自己确定，比如最简单的线性加权函数评价方法，评价值Evalue=w1*minf1(x1,x2)+w2*minf2(x1,x2)，其中w1+w2=1。
总的来说，就是依据自己的需要进行评价，matlab中不含有评价方法（因为评价方法很灵活）。
5. tSp Concorder算法原理
tsp问题遗传算法将多目标按照线性加权的方式转化为单目标，然后应用传统遗传算法求解
其中w_i表示第i个目标的权重，f_k表示归一化之后的第i个目标值。我们很容易知道，这类方法的关键是怎么设计权重。比如，Random Weight Genetic Algorithm (RWGA) 采用随机权重的方式，每次计算适应度都对所有个体随机地产生不同目标的权重，然后进行选择操作。Vector-Evaluated Genetic Algorithm (VEGA) 也是基于线性加权的多目标遗传算法。如果有K个目标，VEGA 会随机地将种群分为K个同等大小子种群，在不同的子种群按照不同的目标函数设定目标值，然后再进行选择操作。VEGA 实质上是基于线性加权的多目标遗传算法。VEGA 是第一个多目标遗传算法，开启了十几年的研究潮流。
1.TSP问题是指假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。本文使用遗传算法解决att30问题，即30个城市的旅行商问题。旅行商问题是一个经典的组合优化问题。一个经典的旅行商问题可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。TSP问题可以分为对称和不对称。在对称TSP问题中，两座城市之间来回的距离是相等的，形成一个无向图，而不对称TSP则形成有向图。对称性TSP问题可以将解的数量减少了一半。所以本次实验的TSP问题使用att48数据，可在tsplib中下载数据包。演化算法是一类模拟自然界遗传进化规律的仿生学算法，它不是一个具体的算法，而是一个算法簇。遗传算法是演化算法的一个分支，由于遗传算法的整体搜索策略和优化计算是不依赖梯度信息，所以它的应用比较广泛。我们本次实验同样用到了遗传算法（用MATLAB编写）来解决TSP问题。
6. nsga2算法全称
NSGA2算法
1、得到：可以看到NSGA-II算法得到的Pareto最优前沿质量很高：最优解均匀分布在不连续前沿的各个线段上；同时在最优前沿以外没有个体存在。
2、NSGA-II特别的地方就在它的选择过程上，其他的和其他算法也没什么区别。选择过程分两个部分： 把种群分成一组Pareto非支配集。一个非支配集里的个体不被当前或之后非支配集里的任何个体支配。
3、遗传算法在matlab里有两个函数，分别是ga和gaoptimset，前者用来调用遗传算法，后者用来设定遗传算法的参数，具体内容可以doc ga查看，遗传算法有哪些参数可以直接在命令窗口输入gaoptimset查看，祝好。
4、针对新生代群体进行交叉和变异操作，以概率的方法判决进行交叉还是变异操作，一般来说，我们以较大的概率交叉，较小的概率进行变异，具体的交叉变异操作文献上都有，和二进制遗传算法是不一样的，一会儿我会讲到。
ncga和nsga-ii遗传算法的区别
1、ncga和nsga-ii遗传算法的区别 1 初始化染色体，这一步和粒子群初始化没啥区别 2 采用二人或多人锦标赛形式，在配对池里产生新的染色体子代，新生代种群规模为原来种群规模的一半。
2、NSGA-II特别的地方就在它的选择过程上，其他的和其他算法也没什么区别。选择过程分两个部分： 把种群分成一组Pareto非支配集。一个非支配集里的个体不被当前或之后非支配集里的任何个体支配。
3、可以看到NSGA-II算法得到的Pareto最优前沿质量很高：最优解均匀分布在不连续前沿的各个线段上；同时在最优前沿以外没有个体存在。
4、基本遗传算法是对交叉后的个体进行变异的，具体你可以看王小平的《遗传算法——理论、应用与软件实现》。
学习多目标优化需要掌握哪些python知识
你需要掌握Python基本语法规则及变量、逻辑控制、内置数据结构、文件操作、高级函数、模块、常用标准库模块、函数、异常处理、MySQL使用、协程等知识点。
学习基本的语法，包括数据结构（数组，字典等）。了解数据类型，以及他的类型转换。2学会流程控制---选择，循环。3函数，模块，熟练使用常用的内建函数。
文件操作：很多时候我们需要对本地文件进行一些增删改查的操作。模块和包：Python之所以如此受欢迎，很大程度上得益于它有非常丰富模块和包，这些东西可以让你少造轮子。
WEB开发 Python拥有很多免费数据函数库、免费web网页模板系统、以及与web服务器进行交互的库，可以实现web开发，搭建web框架，目前比较有名气的Python web框架为Django。
混合遗传算法和遗传算法有什么区别
1、一楼回答的对，混合遗传算法就是将遗传算法与其他算法相混合，互取所长，互补所短。比如遗传算法与模拟退火算法的混合，就是将遗传算法的全局搜索能力与模拟退火算法的局部搜索能力结合起来，形成一种强大的算法。
2、遗传算法是一种全局搜索算法，不需要目标函数的导数信息，它能够很快搜索到最优值所处范围范围。
3、遗传算法是演化算法中的一种。遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。
4、混合遗传就是子代的性状是父本和母本性状的混合，它的后代再也分不出那是父本性状或母本性状了。但孟德尔遗传包括分离定律和自由组合定律，是亲本基因的组合。额，语文水平有限。。
7. 遗传算法-总结
最近在做遗传算法的项目，简单记录一下。
遗传算法是模拟自然界生物进化机制的一种算法，在寻优过程中有用的保留无用的去除。包括3个基本的遗传算子：选择（selection）、交叉（crossover）和变异（mutation）。遗传操作的效果与上述3个遗传算子所取的操作概率、编码方法、群体大小、初始群体，以及适应度函数的设定密切相关。
1、种群初始化
popsize 种群大小，一般为20-100，太小会降低群体的多样性，导致早熟；较大会影响运行效率；迭代次数一般100-500；交叉概率：0.4-0.99，太小会破坏群体的优良模式；变异概率：0.001-0.1，太大搜索趋于随机。编码包括实数编码和二进制编码，可以参考遗传算法的几个经典问题，TSP、背包问题、车间调度问题。
2、选择
目的是把优化个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代，我大部分采用了轮盘赌的方法。具体可参考 http://my.oschina.net/u/1412321/blog/192454 轮盘赌方法各个个体的选择概率和其适应值成比例，个体适应值越大，被选择的概率也越高，反之亦然。在实际问题中，经常需要最小值作为最优解，有以下几种方法进行转换
a、0-1之间的数据，可以用1-该数值，则最小值与最大值互换；
b、 求倒数；
c、求相反数；
以上几种方法均可以将最大值变为最小值，最小值变为最大值，便于利用轮盘赌选择最优个体，根据实际情况来确定。
3、交叉
交叉即将两个父代个体的部分结构加以替换重组而生成新个体的操作，通过交叉，遗传算法的搜索能力得以飞跃提高。根据编码方法的不同，可以有以下的算法：
a、实值重组
离散重组、中间重组、线性重组、扩展线性重组
b、二进制交叉
单点交叉、多点交叉、均匀交叉、洗牌交叉、缩小代理交叉
4、变异
基本步骤：对群中所有个体以事先设定的变异概率判断是否进行变异；对进行变异的个体随机选择变异位进行变异。根据编码表示方法的不同，有实值变异和二进制变异
变异的目的：
a、使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部搜索能力可以加速向最优解收敛。显然该情况下变异概率应取较小值，否则接近最优解的积木块会因为变异遭到破坏。
b、使遗传算法可维持多样性，以防止未成熟收敛现象。此时收敛概率应取较大值。
变异概率一般取0.001-0.1。
5、终止条件
当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设代数一般为100-500。
6、其它
多变量：将多个变量依次连接
多目标：一种方法是转化为单目标，例如按大小进行排序，根据排序和进行选择，可以参考 https://blog.csdn.net/paulfeng20171114/article/details/82454310