遗传算法( GA , Genetic Algorithm ) ，也称进化算法。遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。因此在介绍遗传算法前有必要简单的介绍生物进化知识。
一.进化论知识
作为遗传算法生物背景的介绍，下面内容了解即可：
种群(Population)：生物的进化以群体的形式进行，这样的一个群体称为种群。
个体：组成种群的单个生物。
基因 ( Gene ) ：一个遗传因子。
染色体 ( Chromosome )：包含一组的基因。
生存竞争，适者生存：对环境适应度高的、牛B的个体参与繁殖的机会比较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越来越少。
遗传与变异：新个体会遗传父母双方各一部分的基因，同时有一定的概率发生基因变异。
简单说来就是：繁殖过程，会发生基因交叉( Crossover ) ，基因突变( Mutation ) ，适应度( Fitness )低的个体会被逐步淘汰，而适应度高的个体会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的，其中很可能包含史上产生的适应度最高的那个个体。
二.遗传算法思想
借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。
举个例子，使用遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编码为一串0-1字符串（0：不取，1：取）；首先，随机产生M个0-1字符串，然后评价这些0-1字符串作为0-1背包问题的解的优劣；然后，随机选择一些字符串通过交叉、突变等操作产生下一代的M个字符串，而且较优的解被选中
的概率要比较高。这样经过G代的进化后就可能会产生出0-1背包问题的一个“近似最优解”。
编码：需要将问题的解编码成字符串的形式才能使用遗传算法。最简单的一种编码方式是二进制编码，即将问题的解编码成二进制位数组的形式。例如，问题的解是整数，那么可以将其编码成二进制位数组的形式。将0-1字符串作为0-1背包问题的解就属于二进制编码。
遗传算法有3个最基本的操作：选择，交叉，变异。
选择：选择一些染色体来产生下一代。一种常用的选择策略是“比例选择”，也就是个体被选中的概率与其适应度函数值成正比。假设群体的个体总数是M，那么那么一个体Xi被选中的概率为f(Xi)/( f(X1) + f(X2) + …….. + f(Xn) ) 。比例选择实现算法就是所谓的“轮盘赌算法”( Roulette Wheel Selection ) ，轮盘赌算法的一个简单的实现如下：
轮盘赌算法
/*
* 按设定的概率，随机选中一个个体
* P[i]表示第i个个体被选中的概率
*/
int RWS()
{
m =0;
r =Random(0,1); //r为0至1的随机数
for(i=1;i<=N; i++)
{
/* 产生的随机数在m~m+P[i]间则认为选中了i
* 因此i被选中的概率是P[i]
*/
m = m + P[i];
if(r<=m) return i;
}
}
交叉(Crossover)：2条染色体交换部分基因，来构造下一代的2条新的染色体。例如：
交叉前：
00000|011100000000|10000
11100|000001111110|00101
交叉后：
00000|000001111110|10000
11100|011100000000|00101
染色体交叉是以一定的概率发生的，这个概率记为Pc 。
变异(Mutation)：在繁殖过程，新产生的染色体中的基因会以一定的概率出错，称为变异。变异发生的概率记为Pm 。例如：
变异前：
000001110000000010000
变异后：
000001110000100010000
适应度函数 ( Fitness Function )：用于评价某个染色体的适应度，用f(x)表示。有时需要区分染色体的适应度函数与问题的目标函数。例如：0-1背包问题的目标函数是所取得物品价值，但将物品价值作为染色体的适应度函数可能并不一定适合。适应度函数与目标函数是正相关的，可对目标函数作一些变形来得到适应度函数。
三.基本遗传算法的伪代码
基本遗传算法伪代码
/*
* Pc：交叉发生的概率
* Pm：变异发生的概率
* M：种群规模
* G：终止进化的代数
* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
*/
初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop
do
{
计算种群Pop中每一个体的适应度F(i)。
初始化空种群newPop
do
{
根据适应度以比例选择算法从种群Pop中选出2个个体
if ( random ( 0 , 1 ) < Pc )
{
对2个个体按交叉概率Pc执行交叉操作
}
if ( random ( 0 , 1 ) < Pm )
{
对2个个体按变异概率Pm执行变异操作
}
将2个新个体加入种群newPop中
} until ( M个子代被创建 )
用newPop取代Pop
}until ( 任何染色体得分超过Tf，或繁殖代数超过G )
四.基本遗传算法优化
下面的方法可优化遗传算法的性能。
精英主义(Elitist Strategy)选择：是基本遗传算法的一种优化。为了防止进化过程中产生的最优解被交叉和变异所破坏，可以将每一代中的最优解原封不动的复制到下一代中。
插入操作：可在3个基本操作的基础上增加一个插入操作。插入操作将染色体中的某个随机的片段移位到另一个随机的位置。
五. 使用AForge.Genetic解决TSP问题
https://www.doczj.com/doc/d76045117.html,是一个C#实现的面向人工智能、计算机视觉等领域的开源架构。https://www.doczj.com/doc/d76045117.html,中包含有一个遗传算法的类库。
https://www.doczj.com/doc/d76045117.html,主页：https://www.doczj.com/doc/d76045117.html,/
https://www.doczj.com/doc/d76045117.html,代码下载：https://www.doczj.com/doc/d76045117.html,/p/aforge/
介绍一下AForge的遗传算法用法吧。AForge.Genetic的类结构如下：
图1. AForge.Genetic的类图
下面用AForge.Genetic写个解决TSP问题的最简单实例。测试数据集采用网上流传的中国31个省会城市的坐标:
13042312
36391315
41772244
37121399
34881535
33261556
32381229
41961004
4312790
4386570
30071970
25621756
27881491
23811676
1332695
37151678
39182179
40612370
37802212
36762578
40292838
42632931
34291908
35072367
33942643
34393201
29353240
31403550
25452357
27782826
23702975
操作过程：
(1) 下载https://www.doczj.com/doc/d76045117.html,类库，网址：
https://www.doczj.com/doc/d76045117.html,/p/aforge/downloads/list
(2) 创建C#空项目GenticTSP。然后在AForge目录下找到AForge.dll 和AForge.Genetic.dll，将其拷贝到TestTSP项目的bin/Debug目录下。再通过“Add Reference...”将这两个DLL添加到工程。
(3) 将31个城市坐标数据保存为bin/Debug/Data.txt 。
(4) 添加TSPFitnessFunction.cs，加入如下代码：
TSPFitnessFunction类
using System;
using AForge.Genetic;
namespace GenticTSP
{
///
/// Fitness function for TSP task (TravalingSalasman Problem)
///
publicclass TSPFitnessFunction : IFitnessFunction
{
// map
privateint[,] map =null;
// Constructor
public TSPFitnessFunction(int[,] map)
{
this.map = map;
}
///
/// Evaluate chromosome - calculates its fitness value
///
publicdouble Evaluate(IChromosome chromosome)
{
return1/ (PathLength(chromosome) +1);
}
///
/// Translate genotype to phenotype
///
publicobject Translate(IChromosome chromosome)
return chromosome.ToString();
}
///
/// Calculate path length represented by the specified chromosome
///
publicdouble PathLength(IChromosome chromosome)
{
// salesman path
ushort[] path = ((PermutationChromosome)chromosome).Value;
// check path size
if (path.Length != map.GetLength(0))
{
thrownew ArgumentException("Invalid path specified - not all cities are visited");
}
// path length
int prev = path[0];
int curr = path[path.Length -1];
// calculate distance between the last and the first city
double dx = map[curr, 0] - map[prev, 0];
double dy = map[curr, 1] - map[prev, 1];
double pathLength = Math.Sqrt(dx * dx + dy * dy);
// calculate the path length from the first city to the last
for (int i =1, n = path.Length; i < n; i++)
{
// get current city
curr = path[i];
// calculate distance
dx = map[curr, 0] - map[prev, 0];
dy = map[curr, 1] - map[prev, 1];
pathLength += Math.Sqrt(dx * dx + dy * dy);
// put current city as previous
prev = curr;
}
return pathLength;
}
}
(5) 添加GenticTSP.cs，加入如下代码：
GenticTSP类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using AForge;
using AForge.Genetic;
namespace GenticTSP
{
class GenticTSP
{
staticvoid Main()
{
StreamReader reader =new StreamReader("Data.txt"); int citiesCount =31; //城市数
int[,] map =newint[citiesCount, 2];
for (int i =0; i < citiesCount; i++)
{
string value = reader.ReadLine();
string[] temp = value.Split('');
map[i, 0] =int.Parse(temp[0]); //读取城市坐标
map[i, 1] =int.Parse(temp[1]);
}
// create fitness function
TSPFitnessFunctionfitnessFunction =new TSPFitnessFunction(map);
int populationSize = 1000; //种群最大规模
/*
* 0：EliteSelection算法
* 1：RankSelection算法
* 其他：RouletteWheelSelection 算法
* */
int selectionMethod =0;
// create population
Populationpopulation =new Population(populationSize,
new PermutationChromosome(citiesCount),
fitnessFunction,
(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() : (selectionMethod ==1) ? (ISelectionMethod)new RankSelection() : (ISelectionMethod)new RouletteWheelSelection()
);
// iterations
int iter =1;
int iterations =5000; //迭代最大周期
// loop
while (iter < iterations)
{
// run one epoch of genetic algorithm
population.RunEpoch();
// increase current iteration
iter++;
}
System.Console.WriteLine("遍历路径是： {0}", ((PermutationChromosome)population.BestChromosome).ToString()); System.Console.WriteLine("总路程是：{0}",
fitnessFunction.PathLength(population.BestChromosome)); System.Console.Read();
}
}
}
一需求分析 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．测试数据 输入初始变量后用y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 二概要设计 1．程序流程图 2．类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual
{ char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 4．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个体就被选出，即适应度为fi的个体以fi/∑fk的概率继续存在； 显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。 （4）染色体交叉函数crossoveroperator() 这是遗传算法中的最重要的函数之一，它是对个体两个变量所合成的染色体进行交叉，而不是变量染色体的交叉，这要搞清楚。首先用rand ()函数产生随机概率，若小于交叉概率，则进行染色体交叉，同时交叉次数加1。这时又要用rand()函数随机产生一位交叉位，把染色
硕士生考查课程考试试卷 考试科目： 考生姓名：考生学号： 学院：专业： 考生成绩： 任课老师(签名) 考试日期：年月日午时至时
《MATLAB 教程》试题： A 、利用MATLA B 设计遗传算法程序，寻找下图11个端点最短路径，其中没有连接端点表示没有路径。要求设计遗传算法对该问题求解。 a e h k B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 C 、利用MATLAB 编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？ D 、结合自己的研究方向选择合适的问题，利用MATLAB 进行实验。 以上四题任选一题进行实验，并写出实验报告。
选择题目： B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 一、问题分析（10分） 这是一个简单的三元函数求最小值的函数优化问题，可以利用遗传算法来指导性搜索最小值。实验要求必须以matlab 为工具，利用遗传算法对问题进行求解。 在本实验中，要求我们用M 函数自行设计遗传算法，通过遗传算法基本原理，选择、交叉、变异等操作进行指导性邻域搜索，得到最优解。 二、实验原理与数学模型（20分） （1）试验原理： 用遗传算法求解函数优化问题，遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。 遗传算法是一种现代智能算法，实际上它的功能十分强大，能够用于求解一些难以用常规数学手段进行求解的问题，尤其适用于求解多目标、多约束，且目标函数形式非常复杂的优化问题。但是遗传算法也有一些缺点，最为关键的一点，即没有任何理论能够证明遗传算法一定能够找到最优解，算法主要是根据概率论的思想来寻找最优解。因此，遗传算法所得到的解只是一个近似解，而不一定是最优解。 （2）数学模型 对于求解该问题遗传算法的构造过程： （1）确定决策变量和约束条件；
. % function nsga_2(pro) %% Main Function % Main program to run the NSGA-II MOEA. % Read the corresponding documentation to learn more about multiobjective % optimization using evolutionary algorithms. % initialize_variables has two arguments; First being the population size % and the second the problem number. '1' corresponds to MOP1 and '2' % corresponds to MOP2. %inp_para_definition=input_parameters_definition; %% Initialize the variables % Declare the variables and initialize their values % pop - population % gen - generations % pro - problem number %clear;clc;tic; pop = 100; % 每一代的种群数 gen = 100; % 总共的代数 pro = 2; % 问题选择1或者2，见switch switch pro case 1 % M is the number of objectives. M = 2; % V is the number of decision variables. In this case it is % difficult to visualize the decision variables space while the % objective space is just two dimensional. V = 6; case 2 M = 3; V = 12; case 3 % case 1和case 2 用来对整个算法进行常规验证，作为调试之用；case 3 为本工程所需； M = 2; %(output parameters 个数) V = 8; %(input parameters 个数) K = 10; end % Initialize the population chromosome = initialize_variables(pop,pro); %% Sort the initialized population % Sort the population using non-domination-sort. This returns two columns % for each individual which are the rank and the crowding distance
function youhuafun D=code; N=50;%Tunable maxgen=50;%Tunable crossrate=0.5;%Tunable muterate=0.08;%Tunable generation=1; num=length(D); fatherrand=randint(num,N,3); score=zeros(maxgen,N); while generation<=maxgen ind=randperm(N-2)+2;%随机配对交叉 A=fatherrand(:,ind(1:(N-2)/2)); B=fatherrand(:,ind((N-2)/2+1:end)); %多点交叉 rnd=rand(num,(N-2)/2); ind=rnd tmp=A(ind); A(ind)=B(ind); B(ind)=tmp; %%两点交叉 %for kk=1:(N-2)/2 %rndtmp=randint(1,1,num)+1; %tmp=A(1:rndtmp,kk); %A(1:rndtmp,kk)=B(1:rndtmp,kk); %B(1:rndtmp,kk)=tmp; %end fatherrand=[fatherrand(:,1:2),A,B]; %变异 rnd=rand(num,N); ind=rnd[m,n]=size(ind); tmp=randint(m,n,2)+1; tmp(:,1:2)=0; fatherrand=tmp+fatherrand; fatherrand=mod(fatherrand,3); %fatherrand(ind)=tmp; %评价、选择 scoreN=scorefun(fatherrand,D);%求得N个个体的评价函数 score(generation,:)=scoreN; [scoreSort,scoreind]=sort(scoreN); sumscore=cumsum(scoreSort); sumscore=sumscore./sumscore(end); childind(1:2)=scoreind(end-1:end); for k=3:N tmprnd=rand; tmpind=tmprnd difind=[0,diff(t mpind)]; if~any(difind) difind(1)=1; end childind(k)=scoreind(logical(difind)); end fatherrand=fatherrand(:,childind); generation=generation+1; end %score maxV=max(score,[],2); minV=11*300-maxV; plot(minV,'*');title('各代的目标函数值'); F4=D(:,4); FF4=F4-fatherrand(:,1); FF4=max(FF4,1); D(:,5)=FF4; save DData D function D=code load youhua.mat %properties F2and F3 F1=A(:,1); F2=A(:,2); F3=A(:,3); if(max(F2)>1450)||(min(F2)<=900) error('DATA property F2exceed it''s range (900,1450]') end %get group property F1of data,according to F2value F4=zeros(size(F1)); for ite=11:-1:1 index=find(F2<=900+ite*50); F4(index)=ite; end D=[F1,F2,F3,F4]; function ScoreN=scorefun(fatherrand,D) F3=D(:,3); F4=D(:,4); N=size(fatherrand,2); FF4=F4*ones(1,N); FF4rnd=FF4-fatherrand; FF4rnd=max(FF4rnd,1); ScoreN=ones(1,N)*300*11; %这里有待优化
一个简单实用的遗传算 法c程序 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
一个简单实用的遗传算法c程序（转载） 2009-07-28 23:09:03 阅读418 评论0 字号：大中小 这是一个非常简单的遗传算法源代码，是由Denis Cormier (North Carolina State University)开发的，Sita (University of North Carolina at Charlotte)修正。代码保证尽可能少，实际上也不必查错。对一特定的应用修正此代码，用户只需改变常数的定义并且定义“评价函数”即可。注意代码的设计是求最大值，其中的目标函数只能取正值；且函数值和个体的适应值之间没有区别。该系统使用比率选择、精华模型、单点杂交和均匀变异。如果用Gaussian变异替换均匀变异，可能得到更好的效果。代码没有任何图形，甚至也没有屏幕输出，主要是保证在平台之间的高可移植性。读者可以从,目录 coe/evol中的文件中获得。要求输入的文件应该命名为‘’；系统产生的输出文件为‘’。输入的文件由几行组成：数目对应于变量数。且每一行提供次序——对应于变量的上下界。如第一行为第一个变量提供上下界，第二行为第二个变量提供上下界，等等。 /**************************************************************************/ /* This is a simple genetic algorithm implementation where the */ /* evaluation function takes positive values only and the */ /* fitness of an individual is the same as the value of the */ /* objective function */ /**************************************************************************/ #include <> #include <> #include <> /* Change any of these parameters to match your needs */ #define POPSIZE 50 /* population size */
遗传算法在多目标优化的应用：公式，讨论，概述/总括 概述 本文主要以适合度函数为基础的分配方法来阐述多目标遗传算法。传统的群落形成方法（niche formation method）在此也有适当的延伸,并提供了群落大小界定的理论根据。适合度分配方法可将外部决策者直接纳入问题研究范围，最终通过多目标遗传算法进行进一步总结：遗传算法在多目标优化圈中为是最优的解决方法，而且它还将决策者纳入在问题讨论范围内。适合度分配方法通过遗传算法和外部决策者的相互作用以找到问题最优的解决方案，并且详细解释遗传算法和外部决策者如何通过相互作用以得出最终结果。 1.简介 求非劣解集是多目标决策的基本手段。已有成熟的非劣解生成技术本质上都是以标量优化的手段通过多次计算得到非劣解集。目前遗传算法在多目标问题中的应用方法多数是根据决策偏好信息，先将多目标问题标量化处理为单目标问题后再以遗传算法求解，仍然没有脱离传统的多目标问题分步解决的方式。在没有偏好信息条件下直接使用遗传算法推求多目标非劣解的解集的研究尚不多见。 本文根据遗传算法每代均产生大量可行解和隐含的并行性这一特点，设计了一种基于排序的表现矩阵测度可行解对所有目标总体表现好坏的向量比较方法，并通过在个体适应度定标中引入该方法，控制优解替换和保持种群多样性，采用自适应变化的方式确定交叉和变异概率，设计了多目标遗传算法(Multi Objective Genetic Algorithm, MOGA)。该算法通过一次计算就可以得到问题的非劣解集， 简化了多目标问题的优化求解步骤。 多目标问题中在没有给出决策偏好信息的前提下，难以直接衡量解的优劣，这是遗传算法应用到多目标问题中的最大困难。根据遗传算法中每一代都有大量的可行解产生这一特点，我们考虑通过可行解之间相互比较淘汰劣解的办法来达到最 后对非劣解集的逼近。 考虑一个n维的多目标规划问题，且均为目标函数最大化， 其劣解可以定义为： f i (x * )≤f i (x t ) i=1，2，??，n (1) 且式(1)至少对一个i取“＜”。即至少劣于一个可行解的x必为劣解。 对于遗传算法中产生大量的可行解，我们考虑对同一代中的个体基于目标函数相互比较，淘汰掉确定的劣解，并以生成的新解予以替换。经过数量足够大的种群一定次数的进化计算，可以得到一个接近非劣解集前沿面的解集，在一定精度要求下，可以近似的将其作为非劣解集。 个体的适应度计算方法确定后，为保证能得到非劣解集，算法设计中必须处理好以下问题：(1)保持种群的多样性及进化方向的控制。算法需要求出的是一组不同的非劣解，所以计算中要防止种群收敛到某一个解。与一般遗传算法进化到
多目标遗传算法优化 铣削正交试验结果 说明： 1.建立切削力和表面粗糙度模型 如： 3.190.08360.8250.5640.45410c e p z F v f a a -=（1） a R =此模型你们来拟合（上面有实验数据，剩下的两个方程已经是我帮你们拟合好的了）（2） R a =10?0.92146v c 0.14365f z 0.16065a e 0.047691a p 0.38457 10002/c z p e Q v f a a D π=-????（3） 变量约束范围：401000.020.080.25 1.0210c z e p v f a a ≤≤??≤≤??≤≤? ?≤≤? 公式（1）和（2）值越小越好，公式（3）值越大越好。π=3.14 D=8 2.请将多目标优化操作过程录像（同时考虑三个方程，优化出最优的自变量数值），方便我后续进行修改；将能保存的所有图片及源文件发给我；将最优解多组发给我，类似于下图（黄色部分为达到的要求）
遗传算法的结果:
程序如下: clear; clc; % 遗传算法直接求解多目标优化 D=8; % Function handle to the fitness function F=@(X)[10^(3.19)*(X(1).^(-0.0836)).*(X(2).^0.825).*(X(3).^0.564).*(X(4).^0. 454)]; Ra=@(X)[10^(-0.92146)*(X(1).^0.14365).*(X(2).^0.16065).*(X(3).^0.047691).*( X(4).^0.38457)]; Q=@(X)[-1000*2*X(1).*X(2).*X(3).*X(4)/(pi*D)];
函数最值问题：F=X2+Y2-Z2, clear clc %%初始化 pc=0.9; %交叉概率 pm=0.05; %变异概率 popsize=500; chromlength1=21; chromlength2=23; chromlength3=20; chromlength=chromlength1+chromlength2+chromlength3; pop=initpop(popsize,chromlength);% 产生初始种群 for i=1:500 [objvalue]=calobjvalue(pop); %计算目标函数值 [fitvalue]=calfitvalue(objvalue);%计算个体适应度 [newpop]=selection(pop,fitvalue);%选择 [newpop1]=crossover(newpop,pc) ; %交叉 [newpop2]=mutation(newpop1,pm) ;%变异 [newobjvalue]=newcalobjvalue(newpop2); %计算最新代目标函数值 [newfitvalue]=newcalfitvalue(newobjvalue); % 计算新种群适应度值[bestindividual,bestfit]=best(newpop2,newfitvalue); %求出群体中适应值最大的个体及其适应值 y(i)=max(bestfit); %储存最优个体适应值 pop5=bestindividual; %储存最优个体 n(i)=i; %记录最优代位置 %解码 x1(i)=0+decodechrom(pop5,1,21)*2/(pow2(21)-1); x2(i)=decodechrom(pop5,22,23)*6/(pow2(23)-1)-1; x3(i)=decodechrom(pop5,45,20)*1/(pow2(20)-1); pop=newpop2; end %%绘图 figure(1)%最优点变化趋势图 i=1:500; plot(y(i),'-b*') xlabel('迭代次数'); ylabel('最优个体适应值'); title('最优点变化趋势'); legend('最优点');
一种在复杂网络中发现社区的多目标遗传算法 Clara Pizzuti 摘要——本文提出了一种揭示复杂网络社区结构的多目标遗传算法。该算法优化了两个目标函数，这些函数能够识别出组内节点密集连接，而组间连接稀疏。该方法能产生一系列不同等级的网络社区，其中解的等级越高，由更多的社区组成，被包含在社区较少的解中。社区的数量是通过目标函数更佳的折衷值自动确定的。对合成和真实网络的实验，结果表明算法成功地检测到了网络结构，并且能与最先进的方法相比较。 关键词：复杂网络，多目标聚类，多目标进化算法 1、简介 复杂网络构成了表示组成许多真实世界系统的对象之间关系的有效形式。协作网络、因特网、万维网、生物网络、通信传输网络，社交网络只是一些例子。将网络建模为图，节点代表个体，边代表这些个体之间的联系。 复杂网络研究中的一个重要问题是社区结构[25]的检测，也被称作为聚类[21]，即将一个网络划分为节点组，称作社区或簇或模块，组内连接紧密，组间连接稀疏。这个问题，如[21]指出，只有在建模网络的图是稀疏的时候才有意义，即边的数量远低于可能的边数，否则就类似于数据簇[31]。图的聚类不同于数据聚类，因为图中的簇是基于边的密度，而在数据聚类中，它们是与距离或相似度量紧密相关的组点。然而，网络中社区的概念并未严格定义，因为它的定义受应用领域的影响。因此，直观的理解是同一社区内部边的数量应该远多于连接图中剩余节点的边的数量，这构成了社区定义的一般建议。这个直观定义追求两个不同的目标：最大化内部连接和最小化外部连接。 多目标优化是一种解决问题的技术，当多个相互冲突的目标被优化时，成功地找到一组解。通过利用帕累托最优理论[15]获得这些解，构成了尽可能满足所有目标的全局最优解。解决多目标优化问题的进化算法取得成功，是因为它们基于种群的特性，同时产生多个最优解和一个帕累托前沿[5]的优良近似。 因此，社区检测能够被表述为多目标优化问题，并且帕累托最优性的框架可以提供一组解对应于目标之间的最佳妥协以达到最优化。事实上，在上述两个目标之间有一个折衷，因为当整个网络社区结构的外部连接数量为空时，那它就是最小的，然而簇密度不够高。 在过去的几年里，已经提出了许多方法采用多目标技术进行数据聚类。这些方法大部分在度量空间[14], [17],[18], [28], [38], [39], [49], [51]聚集目标，虽然[8]中给出了分割图的一个方法，并且在[12]中描述了网络用户会议的一个图聚类算法。 本文中，一个多目标方法，名为用于网络的多目标遗传算法(MOGA-Net)，通过利用提出的遗传算法发现网络中的社区。该方法优化了[32]和[44]中介绍的两个目标函数，它们已被证实在检测复杂网络中模块的有效性。第一个目标函数利用了community score的概念来衡量对一个网络进行社区划分的质量。community score值越高，聚类密度越高。第二个目标函数定义了模块中节点fitness的概念，并且反复迭代找到节点fitness总和最大的模块，以下将这个目标函数称为community fitness。当总和达到最大时，外部连接是最小。两个目标函数都有一个正实数参数控制社区的规模。参数值越大，找到的社区规模越小。MOGA-Net利用这两个函数的优点，通过有选择地探索搜寻空间获得网络中存在的社区，而不需要提前知道确切的社区数目。这个数目是通过两个目标之间的最佳折衷自动确定的。 多目标方法的一个有趣结果是它提供的不是一个单独的网络划分，而是一组解。这些解中的每一个都对应两个目标之间不同的折衷，并对应多种网络划分方式，即由许多不同簇组成。对合成网络和真实网络的实验表明，这一系列帕累托最优解揭示了网络的分层结构，其中簇的数目较多的解包含在社区数目较少的解中。多目标方法的这个特性提供了一个很好的机会分析不同层级
C语言遗传算法代码 以下为遗传算法的源代码，计算一元代函数的代码和二元函数的代码以+++++++++++++++++++++++++++++++++++++为分割线分割开来，请自行选择适合的代码，使用时请略看完代码的注释，在需要更改的地方更改为自己需要的代码。 +++++++++++++++++++++++++++++++一元函数代码++++++++++++++++++++++++++++ #include
遗传算法的C语言程序案例 一、说明 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．举个例子，输入初始变量后，用y= (x1*x1)+(x2*x2)，其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 4．程序流程图
5．类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual { char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 6．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个
遗传算法经典学习Matlab代码 遗传算法实例: 也是自己找来的，原代码有少许错误，本人都已更正了，调试运行都通过了的。对于初学者，尤其是还没有编程经验的非常有用的一个文件 遗传算法实例 % 下面举例说明遗传算法 % % 求下列函数的最大值 % % f(x)=10*sin(5x)+7*cos(4x) x∈[0,10] % % 将 x 的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为 (10-0)/(2^10-1)≈0.01 。 % % 将变量域 [0,10] 离散化为二值域 [0,1023], x=0+10*b/1023, 其 中 b 是 [0,1023] 中的一个二值数。 % % %
%--------------------------------------------------------------------------------------------------------------% %--------------------------------------------------------------------------------------------------------------% % 编程 %----------------------------------------------- % 2.1初始化(编码) % initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)， % 长度大小取决于变量的二进制编码的长度(在本例中取10位)。 %遗传算法子程序 %Name: initpop.m %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); % rand随机产生每个单元 为 {0,1} 行数为popsize，列数为chromlength的矩阵，
% function nsga_2(pro) %% Main Function % Main program to run the NSGA-II MOEA. % Read the corresponding documentation to learn more about multiobjective % optimization using evolutionary algorithms. % initialize_variables has two arguments; First being the population size % and the second the problem number. '1' corresponds to MOP1 and '2' % corresponds to MOP2. %inp_para_definition=input_parameters_definition; %% Initialize the variables % Declare the variables and initialize their values % pop - population % gen - generations % pro - problem number %clear;clc;tic; pop = 100; % 每一代的种群数 gen = 100; % 总共的代数 pro = 2; % 问题选择1或者2，见switch switch pro case 1 % M is the number of objectives. M = 2; % V is the number of decision variables. In this case it is % difficult to visualize the decision variables space while the % objective space is just two dimensional. V = 6; case 2 M = 3; V = 12; case 3 % case 1和case 2 用来对整个算法进行常规验证，作为调试之用；case 3 为本工程所需； M = 2; %(output parameters 个数) V = 8; %(input parameters 个数) K = 10; end % Initialize the population chromosome = initialize_variables(pop,pro); %% Sort the initialized population % Sort the population using non-domination-sort. This returns two columns % for each individual which are the rank and the crowding distance % corresponding to their position in the front they belong. 真是牛X了。 chromosome = non_domination_sort_mod(chromosome,pro); %% Start the evolution process
NSGA-II 算法实例 目前的多目标优化算法有很多, Kalyanmoy Deb 的带精英策略的快速非支配排序遗传算法(NSGA-II) 无疑是其中应用最为广泛也是最为成功的一种。本文用的算法是MATLAB 自带的函数gamultiobj ，该函数是基于NSGA-II 改进的一种多目标优化算法。 一、 数值例子 多目标优化问题 424221********* 4224212212112 12min (,)10min (,)55..55 f x x x x x x x x x f x x x x x x x x x s t x =-++-=-++-≤≤??-≤≤? 二、 Matlab 文件 1． 适应值函数m 文件： function y=f(x) y(1)=x(1)^4-10*x(1)^2+x(1)*x(2)+x(2)^4-x(1)^2*x(2)^2; y(2)=x(2)^4-x(1)^2*x(2)^2+x(1)^4+x(1)*x(2); 2． 调用gamultiobj 函数，及参数设置： clear clc fitnessfcn=@f; %适应度函数句柄 nvars=2; %变量个数 lb=[-5,-5]; %下限 ub=[5,5]; %上限 A=[];b=[]; %线性不等式约束 Aeq=[];beq=[]; %线性等式约束 options=gaoptimset('paretoFraction',0.3,'populationsize',100,'generations', 200,'stallGenLimit',200,'TolFun',1e-100,'PlotFcns',@gaplotpareto); % 最优个体系数paretoFraction 为0.3；种群大小populationsize 为100，最大进化代数generations 为200， % 停止代数stallGenLimit 为200， 适应度函数偏差TolFun 设为1e-100，函数gaplotpareto ：绘制Pareto 前端 [x,fval]=gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options)
30维线性方程求解 摘要：非线性方程组的求解是数值计算领域中最困难的问题，大多数的数值求解算法例如牛顿法的收敛性和性能特征在很大程度上依赖于初始点。但是对于很多高维的非线性方程组，选择好的初始点是一件非常困难的事情。本文采用了遗传算法的思想，提出了一种用于求解非线性方程组的混合遗传算法。该混合算法充分发挥了遗传算法的群体搜索和全局收敛性。选择了几个典型非线性方程组，考察它们的最适宜解。 关键词：非线性方程组；混合遗传算法；优化 1. 引言遗传算法是一种通用搜索算法，它基于自然选择机制和自然遗传规律来模拟自然界的进化过程，从而演化出解决问题的最优方法。它将适者生存、结构化但同时又是 随机的信息交换以及算法设计人的创造才能结合起来，形成一种独特的搜索算法，把一些解决方案用一定的方式来表示，放在一起成为群体。每一个方案的优劣程度即为适应性，根据自然界进化“优胜劣汰”的原则，逐步产生它们的后代，使后代具有更强的适应性，这样不断演化下去，就能得到更优解决方案。 随着现代自然科学和技术的发展，以及新学科、新领域的出现，非线性科学在工农业、经济政治、科学研究方面逐渐占有极其重要的位置。在理论研究和应用实践中，几乎绝大多数的问题都最终能化为方程或方程组，或者说，都离不开方程和方程组的求解。因此，在非线性问题中尤以非线性方程和非线性方程组的求解最为基本和重要。传统的解决方法，如简单迭代法、牛顿法、割线法、延拓法、搜索法、梯度法、共轭方向法、变尺度法，无论从算法的选择还是算法本身的构造都与所要解决的问题的特性有很大的关系。很多情况下,算法中算子的构造及其有效性成为我们解决问题的巨大障碍。而遗传算法无需过多地考虑问题的具体形式，因为它是一种灵活的自适应算法，尤其在一些非线性方程组没有精确解的时候，遗传算法显得更为有效。而且，遗传算法是一种高度并行的算法，且算法结构简单，非常便于在计算机上实现。本文所研究的正是将遗传算法应用于求解非线性方程组的问题。 2. 遗传算法解非线性方程组为了直观地观察用遗传算法求解非线性方程组的效果，我们这里用代数非线性方程组作为求解的对象问题描述：非线性方程组指的是有n 个变量（为了简化讨论，这里只讨论实变量方程组）的方程组 中含有非线性方程。其求解是指在其定义域内找出一组数能满足方程组中的每 个方程。这里，我们将方程组转化为一个函数则求解方程组就转化为求一组值使得成立。即求使函数取得最小值0 的一组数，于是方程组求解问题就转变为函数优化问题 3. 遗传算子 遗传算子设计包括交叉算子、变异算子和选择算子的设计。
一．问题描述： 在某一区域内有n 个客户，拟建一个物流中心，已知客户j 地址坐标为),(i i y x 。确定物流中心的地址坐标),(y x ，使得该物流中心到几个客户之间的距离最短。 假设：简单的用两点之间的距离代替运输距离。 目标函数： 22)()(min i i y Y x X z -+-= 约束条件： } 8,7,6,5,4,3,2,1,0{}8,7,6,5,4,3,2,1,0{X ∈∈Y 假设某一区域内有 5 个客户，其位置坐标如下表所示， 客户坐标及相关需求量 客户 X （km) Y(km) 1 1 5 2 2 8 3 5 1 4 7 6 5 8 3 （1）变量： C ：是一个1*6数组，每个数组里面是一个6位二进制数，它是遗传算法中的染色体。 new_c:每一轮的新变量c 。 first_c:初始群体矩阵。 sur_value ：个体适应值的概率值，为0-1之间的数，所有概率值和为1。 survived ：经过选择运算后产生的个体基因型组合。 intersect_c ：经过交叉运算后产生的个体基因型组合。 mutation_c ：经过变异运算后产生的个体基因型组合。 f ：最后计算得到的最大值 （2）程序里面的方程 function out = value_function( ci )：价值函数（自适应度函数）。 function [ sur_value ] = calc_value( c )：计算群体中每一个个体的适应度的值 function survived = surviver( sur_value )：利用概率选择函数 function [ intersect_c ] = intersect( new_c )：交叉运算 function [ mutation_c ,mutation_value] = mutation( intersect_c )：变异运算 （1）遗传算法主程序 %遗传算法的主程序