遗传算法

aimisiyou · 发表于 2018-1-26 12:18:29

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

内容转自http://www.360doc.cn/article/13726687_453806200.html

遗传算法入门例子和总结

南氏珍藏来源

阅11054转2032015-03-09

[url=]收藏[/url]

目录:
  一.写在前面
  二.遗传算法概述
  三.一个简单问题描述
  四.C语言实现
---------------------------------------------------------------------

  一.写在前面
下面的列子是摘自《遗传算法原理与应用》一书，具体PDF下载：http://download.csdn.net/source/1615358  我看了一遍，通俗易懂，很适合入门，有需要的朋友可以下载来看看：）,希望这篇文章对初学者有益 ,转载请注明出处

二.遗传算法概述

遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解
基本组成为:
a.编码(产生初始种群)
b.适应度函数
c.遗传算子(selection, crossover, mutation)
d.运行参数

三.一个简单问题描述

为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各
个主要执行步骤。

   例：求下述二元函数的最大值：

[url=][/url]

(1) 个体编码
         遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种
   符号串。本题中，用无符号二进制整数来表示。
         因 x1, x2 为 0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它
   们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可
   行解。
         例如，基因型 X＝101110 所对应的表现型是：x＝[ 5，6 ]。
         个体的表现型x和基因型X之间可通过编码和解码程序相互转换。
(2) 初始群体的产生
      遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始
   群体数据。
      本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机
   方法产生。
      如：011101，101011，011100，111001

(3) 适应度汁算
      遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传
   机会的大小。
      本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接
   利用目标函数值作为个体的适应度。
(4)  选择运算
      选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代
   群体中。
本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中
   的数量。其具体操作过程是：
      ·  先计算出群体中所有个体的适应度的总和  ?fi  ( i=1.2,…,M );
      ·  其次计算出每个个体的相对适应度的大小 fi / ?fi ，它即为每个个体被遗传
         到下一代群体中的概率，
      ·  每个概率值组成一个区域，全部概率值之和为1；
      ·  最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区
         域内来确定各个个体被选中的次数。

[url=][/url]

(5)  交叉运算
      交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某
两个个体之间的部分染色体。
   本例采用单点交叉的方法，其具体操作过程是：
   · 先对群体进行随机配对；
   · 其次随机设置交叉点位置；
   · 最后再相互交换配对染色体之间的部分基因。

[url=][/url]

(6)  变异运算
      变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进
   行改变，它也是产生新个体的一种操作方法。
      本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：
      · 首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，
      其中的数字表示变异点设置在该基因座处；
      · 然后依照某一概率将变异点的原有基因值取反。

[url=][/url]

对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。

[url=][/url]

从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得
到了明显的改进。事实上，这里已经找到了最佳个体“111111”。
[注意]
      需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，
我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中
有可能需要一定的循环次数才能达到这个最优结果。

[url=][/url]

四.C语言实现

[cpp] view plaincopy

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/////////////The definiton of user data////
#define Cmax 100 //certain maximal value
#define Cmin 0 //certain minimum value
#define LENGHT1 3 //the chromosome length of 1st variable
#define LENGHT2 3 //the chromosome length of 2nd variable
//总染体长度
#define CHROMLENGTH LENGHT1+LENGHT2
const int MaxGeneration = 100; //最大代数
const int PopSize = 10; //样本大小
const double Pc = 0.6; //交叉概率
const double Pm = 0.001; //变异概率
////////////// 数据结构定义///////////////////
struct Individual{
char chrom[CHROMLENGTH + 1]; //一个个体的染色体
double value; //目标值
double fitness; //适应度
};
int generation ; //进化次数
int bestIndex; //最好个体的下标
int worstIndex; //最坏个体的游标
Individual bestIndividual ; //当前一代中的最好个体
Individual worstIndividual ; ///当前一代中的坏个体
// best individual by now
Individual currentBest ;// 到目前为止的最好个体
Individual population [PopSize] ;//样本
///////////////////////
void generateInitialPopulation();
void generateNextPopulation();
void evalutePopulation();
long decomdeChromosome(char*, int, int);
void calculateObjectValue();
void calculateFitnessValue();
void findBestAndWorstIndividual();
void performEvolution();
void selectionOperator();
void crossoverOperator();
void mutationOperator();
void outputTextReport();
//////////////////////////////////////////////
int main(){
generation = 0;
generateInitialPopulation();
evalutePopulation();
while (generation < MaxGeneration) {
generation++;
generateNextPopulation();
evalutePopulation();
performEvolution();
outputTextReport();
}
return 0;
}
//////////////////////////////////////////////////////////////
//////产生第一代样本/////
void generateInitialPopulation() {
int i, j;
srand((unsigned)time(NULL));
for (i = 0; i < PopSize; i++) {
for (j = 0; j < CHROMLENGTH; j++) {
population.chrom[j] = ((rand() % 10) < 5) ? '0' : '1';
}
population.chrom[CHROMLENGTH] = '/0';
}
}
////////产生下一代样本 //////
void generateNextPopulation() {
selectionOperator();
crossoverOperator();
mutationOperator();
}
//变异算子//
void mutationOperator() {
int i, j;
double p;
// bit mutation
for (i = 0; i < PopSize; i++) {
for (j = 0; j < CHROMLENGTH; j++) {
p = rand() % 1000 / 1000.0;
if (p < Pm) {
population.chrom[j] = (population.chrom[j] == '0') ? '1': '0';
}
}
}
}
//交叉算子///
void crossoverOperator() {
int i, j;
int index[PopSize];
int point, temp;
double p;
char ch;
for (i = 0; i < PopSize; i++) {
index = i;
}
for (i = 0; i < PopSize; i++) {
point = rand() %(PopSize - i);
temp = index;
index = index[point + i];
index[point + i] = temp;
}
for (i = 0; i < PopSize - 1; i+=2) {
p = rand() % 1000 / 1000.0;
if (p < Pc) {
point = rand()% (CHROMLENGTH - 1) + 1;
for (j = point; j < CHROMLENGTH; j++) {
ch = population[index].chrom[j];
population[index].chrom[j] = population[index[i + 1]].chrom[j];
population[index[i + 1]].chrom[j] = ch;
}
}
}
}
///选择算子/////////////
void selectionOperator() {
int i, index;
double p, sum = 0.0;
double cfitness[PopSize];
Individual newpopulation[PopSize];
for (i = 0; i < PopSize; i++) {
sum += population.fitness;
}
for (i = 0; i < PopSize; i++) {
cfitness = population.fitness / sum;
}
// calculate cumulative fitness
for (i = 1; i < PopSize; i++) {
cfitness = cfitness + cfitness[i - 1];
}
for (i = 0; i < PopSize; i++) {
p = rand() % 1000 / 1000.0;
index = 0;
while (p > cfitness[index]) {
index++;
}
newpopulation = population[index];
}
for (i = 0; i < PopSize; i++) {
population = newpopulation;
}
}
/////依据某些公式对样本进行评价////
void evalutePopulation() {
calculateObjectValue();
calculateFitnessValue();
findBestAndWorstIndividual();
}
//找出到目前为止最好的个体//////
void findBestAndWorstIndividual() {
int i;
double sum = 0.0;
bestIndividual = population[0];
worstIndividual = population[0];
for (i = 0; i < PopSize; i++) {
if (population.fitness > bestIndividual.fitness) {
bestIndividual = population;
bestIndex = i;
} else if (population.fitness < worstIndividual.fitness) {
worstIndividual = population;
worstIndex = i;
}
sum += population.fitness;
}
if (generation == 0) {
currentBest = bestIndividual;
} else {
if (bestIndividual.fitness > currentBest.fitness) {
currentBest = bestIndividual;
}
}
}
//计算适应度///
void calculateFitnessValue() {
int i;
long temp1, temp2;
double x1, x2;
for (i = 0; i < PopSize; i++) {
temp1 = decomdeChromosome(population.chrom, 0, LENGHT1);
temp2 = decomdeChromosome(population.chrom, LENGHT1, LENGHT2);
x1 = temp1 * temp1;
x2 = temp2 * temp2;
population.fitness = x1+x2;
}
}
//计算目标值
//目标函数为f(x) = x1* x1 + x2*x2
void calculateObjectValue() {
int i;
long temp1, temp2;
double x1, x2;
for (i = 0; i < PopSize; i++) {
temp1 = decomdeChromosome(population.chrom, 0, LENGHT1);
temp2 = decomdeChromosome(population.chrom, LENGHT1, LENGHT2);
x1 = temp1 * temp1;
x2 = temp2 * temp2;
population.value = x1 + x2;
}
}
//把二进制转化为十进制
long decomdeChromosome(char* string, int point, int length) {
int i;
long decimal = 0L;
char * pointer;
for(i = 0, pointer=string+point; i < length;i++,pointer++){
decimal += (*pointer - '0') << (length - 1 - i);
}
return decimal;
}
//进经同时把最坏个体用目前最好个人替代///
void performEvolution() {
if (bestIndividual.fitness > currentBest.fitness) {
currentBest = population[bestIndex];
} else {
population[worstIndex] = currentBest;
}
}
//打印当前样本信息///
void outputTextReport() {
int i;
double sum;
double average;
sum = 0.0;
for (i = 0; i < PopSize; i++) {
sum += population.value;
}
average = sum / PopSize;
printf("gen=%d, avg=%f, best=%f",generation, average,currentBest.value);
printf(" chromosome=");
for( i = 0; i < CHROMLENGTH; i++){
printf("%c", currentBest.chrom);
}
printf("/n");
}

输出结果:
[c-sharp] view plaincopy

gen=1, avg=51.400000, best=74.000000 chromosome=101111
gen=2, avg=58.300000, best=74.000000 chromosome=101111
gen=3, avg=66.300000, best=74.000000 chromosome=101111
gen=4, avg=71.400000, best=74.000000 chromosome=101111
gen=5, avg=75.100000, best=98.000000 chromosome=111111
gen=6, avg=83.600000, best=98.000000 chromosome=111111
gen=7, avg=88.400000, best=98.000000 chromosome=111111
gen=8, avg=90.800000, best=98.000000 chromosome=111111
gen=9, avg=93.200000, best=98.000000 chromosome=111111
gen=10, avg=98.000000, best=98.000000 chromosome=111111
gen=11, avg=98.000000, best=98.000000 chromosome=111111
gen=12, avg=98.000000, best=98.000000 chromosome=111111
gen=13, avg=98.000000, best=98.000000 chromosome=111111
gen=14, avg=98.000000, best=98.000000 chromosome=111111
gen=15, avg=98.000000, best=98.000000 chromosome=111111
gen=16, avg=98.000000, best=98.000000 chromosome=111111
gen=17, avg=98.000000, best=98.000000 chromosome=111111
gen=18, avg=98.000000, best=98.000000 chromosome=111111
gen=19, avg=98.000000, best=98.000000 chromosome=111111
gen=20, avg=98.000000, best=98.000000 chromosome=111111
gen=21, avg=98.000000, best=98.000000 chromosome=111111
gen=22, avg=98.000000, best=98.000000 chromosome=111111
gen=23, avg=98.000000, best=98.000000 chromosome=111111
gen=24, avg=98.000000, best=98.000000 chromosome=111111
gen=25, avg=98.000000, best=98.000000 chromosome=111111
gen=26, avg=98.000000, best=98.000000 chromosome=111111
gen=27, avg=98.000000, best=98.000000 chromosome=111111
gen=28, avg=98.000000, best=98.000000 chromosome=111111
gen=29, avg=98.000000, best=98.000000 chromosome=111111
gen=30, avg=98.000000, best=98.000000 chromosome=111111
gen=31, avg=98.000000, best=98.000000 chromosome=111111
gen=32, avg=98.000000, best=98.000000 chromosome=111111
gen=33, avg=98.000000, best=98.000000 chromosome=111111
gen=34, avg=98.000000, best=98.000000 chromosome=111111
gen=35, avg=98.000000, best=98.000000 chromosome=111111
gen=36, avg=98.000000, best=98.000000 chromosome=111111
gen=37, avg=98.000000, best=98.000000 chromosome=111111
gen=38, avg=98.000000, best=98.000000 chromosome=111111
gen=39, avg=98.000000, best=98.000000 chromosome=111111
gen=40, avg=98.000000, best=98.000000 chromosome=111111
gen=41, avg=98.000000, best=98.000000 chromosome=111111
gen=42, avg=98.000000, best=98.000000 chromosome=111111
gen=43, avg=98.000000, best=98.000000 chromosome=111111
gen=44, avg=98.000000, best=98.000000 chromosome=111111
gen=45, avg=98.000000, best=98.000000 chromosome=111111
gen=46, avg=98.000000, best=98.000000 chromosome=111111
gen=47, avg=98.000000, best=98.000000 chromosome=111111
gen=48, avg=98.000000, best=98.000000 chromosome=111111
gen=49, avg=98.000000, best=98.000000 chromosome=111111
gen=50, avg=98.000000, best=98.000000 chromosome=111111
gen=51, avg=98.000000, best=98.000000 chromosome=111111
gen=52, avg=98.000000, best=98.000000 chromosome=111111
gen=53, avg=98.000000, best=98.000000 chromosome=111111
gen=54, avg=98.000000, best=98.000000 chromosome=111111
gen=55, avg=98.000000, best=98.000000 chromosome=111111
gen=56, avg=98.000000, best=98.000000 chromosome=111111
gen=57, avg=98.000000, best=98.000000 chromosome=111111
gen=58, avg=98.000000, best=98.000000 chromosome=111111
gen=59, avg=98.000000, best=98.000000 chromosome=111111
gen=60, avg=98.000000, best=98.000000 chromosome=111111
gen=61, avg=98.000000, best=98.000000 chromosome=111111
gen=62, avg=98.000000, best=98.000000 chromosome=111111
gen=63, avg=98.000000, best=98.000000 chromosome=111111
gen=64, avg=98.000000, best=98.000000 chromosome=111111
gen=65, avg=98.000000, best=98.000000 chromosome=111111
gen=66, avg=98.000000, best=98.000000 chromosome=111111
gen=67, avg=98.000000, best=98.000000 chromosome=111111
gen=68, avg=98.000000, best=98.000000 chromosome=111111
gen=69, avg=98.000000, best=98.000000 chromosome=111111
gen=70, avg=98.000000, best=98.000000 chromosome=111111
gen=71, avg=98.000000, best=98.000000 chromosome=111111
gen=72, avg=98.000000, best=98.000000 chromosome=111111
gen=73, avg=98.000000, best=98.000000 chromosome=111111
gen=74, avg=98.000000, best=98.000000 chromosome=111111
gen=75, avg=98.000000, best=98.000000 chromosome=111111
gen=76, avg=98.000000, best=98.000000 chromosome=111111
gen=77, avg=98.000000, best=98.000000 chromosome=111111
gen=78, avg=98.000000, best=98.000000 chromosome=111111
gen=79, avg=98.000000, best=98.000000 chromosome=111111
gen=80, avg=98.000000, best=98.000000 chromosome=111111
gen=81, avg=98.000000, best=98.000000 chromosome=111111
gen=82, avg=98.000000, best=98.000000 chromosome=111111
gen=83, avg=98.000000, best=98.000000 chromosome=111111
gen=84, avg=98.000000, best=98.000000 chromosome=111111
gen=85, avg=98.000000, best=98.000000 chromosome=111111
gen=86, avg=98.000000, best=98.000000 chromosome=111111
gen=87, avg=98.000000, best=98.000000 chromosome=111111
gen=88, avg=98.000000, best=98.000000 chromosome=111111
gen=89, avg=98.000000, best=98.000000 chromosome=111111
gen=90, avg=98.000000, best=98.000000 chromosome=111111
gen=91, avg=98.000000, best=98.000000 chromosome=111111
gen=92, avg=98.000000, best=98.000000 chromosome=111111
gen=93, avg=98.000000, best=98.000000 chromosome=111111
gen=94, avg=98.000000, best=98.000000 chromosome=111111
gen=95, avg=98.000000, best=98.000000 chromosome=111111
gen=96, avg=98.000000, best=98.000000 chromosome=111111
gen=97, avg=98.000000, best=98.000000 chromosome=111111
gen=98, avg=98.000000, best=98.000000 chromosome=111111
gen=99, avg=98.000000, best=98.000000 chromosome=111111
gen=100, avg=98.000000, best=98.000000 chromosome=111111
请按任意键继续. . .

从结果可以看出,遗传算法收敛得非常快,在第5代的时候,已经达到了全局最优解.如果把初始种群扩大,收敛得会更快.
遗传算法主要应用领域:
（1）组合优化    （2）函数优化
（3）自动控制    （4）生产调度
（5）图像处理    （6）机器学习
（7）人工生命    （8）数据挖掘

[url=]1[/url]
[url=]1[/url]
[url=]收藏[/url]分享
来自：南氏珍藏  > 《遗传算法》

ynhh · 发表于 2018-1-26 12:25:10

请教
您那个排版的搞出来了吗

aimisiyou · 发表于 2018-1-26 12:27:20

说实话，以前真的不怎么喜欢遗传算法，但凡问题能有其他方式解决一般都不考虑遗传算法，因为觉得遗传算法中编码、选择、交差、变异，解码太繁琐了。

aimisiyou · 发表于 2018-1-26 12:37:04

本帖最后由 aimisiyou 于 2018-1-26 12:38 编辑

ynhh 发表于 2018-1-26 12:25

排版问题的类型很多，没有统一的模式。
现在只能算基本完成个体出图，但要从众多个体组成的群体中找出接近最优还没完成。

VBAVBAA · 发表于 2018-1-26 17:55:27

我也很期待排版问题。。。

yangjian001 · 发表于 2018-1-28 08:55:32

染色体模式所进行的一系列运算

追风lisp · 发表于 2018-1-28 09:59:45

学习了，谢谢分享

aimisiyou · 发表于 2018-1-30 22:12:29

python实现的遗传算法实例（一）发表于2014/4/12 16:34:36 20625人阅读分类： python 算法一、遗传算法介绍遗传算法是通过模拟大自然中生物进化的历程，来解决问题的。大自然中一个种群经历过若干代的自然选择后，剩下的种群必定是适应环境的。把一个问题所有的解看做一个种群，经历过若干次的自然选择以后，剩下的解中是有问题的最优解的。当然，只能说有最优解的概率很大。这里，我们用遗传算法求一个函数的最大值。 f(x) = 10 * sin( 5x ) + 7 * cos( 4x ), 0 <= x <= 10 1、将自变量x进行编码取基因片段的长度为10, 则10位二进制位可以表示的范围是0到1023。基因与自变量转变的公式是x = b2d(individual) * 10 / 1023。构造初始的种群pop。每个个体的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1] 2、计算目标函数值根据自变量与基因的转化关系式，求出每个个体的基因对应的自变量，然后将自变量代入函数f（x），求出每个个体的目标函数值。 3、适应度函数适应度函数是用来评估个体适应环境的能力，是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成0. 因为我们求的是最大值，所以要使目标函数值是负数的个体不适应环境，使其繁殖后代的能力为0.适应度函数的作用将在自然选择中体现。 4、自然选择自然选择的思想不再赘述，操作使用轮盘赌算法。其具体步骤：假设种群中共5个个体，适应度函数计算出来的个体适应性列表是fitvalue = [1 ,3, 0, 2, 4] ，totalvalue = 10 ，如果将fitvalue画到圆盘上，值的大小表示在圆盘上的面积。在转动轮盘的过程中，单个模块的面积越大则被选中的概率越大。选择的方法是将fitvalue转化为[1 ， 4 ，4 , 6 ，10], fitvalue / totalvalue = [0.1 , 0.4 , 0.4 , 0.6 , 1.0] . 然后产生5个0-1之间的随机数，将随机数从小到大排序，假如是[0.05 , 0.2 , 0.7 , 0.8 ,0.9]，则将0号个体、1号个体、4号个体、4号个体、4号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。 5、繁殖假设个体a、b的基因是 a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0] b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1] 这两个个体发生基因交换的概率pc = 0.6.如果要发生基因交换，则产生一个随机数point表示基因交换的位置，假设point = 4,则： a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0] b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1] 交换后为： a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1] b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0] 6、突变遍历每一个个体，基因的每一位发生突变（0变为1,1变为0）的概率为0.001.突变可以增加解空间二、代码 def b2d(b): #将二进制转化为十进制 x∈[0,10] t = 0 for j in range(len(b)): t += b[j] * (math.pow(2, j)) t = t * 10 / 1023 return t popsize = 50 #种群的大小 #用遗传算法求函数最大值： #f(x)=10*sin(5x)+7*cos(4x) x∈[0,10] chromlength = 10 #基因片段的长度 pc = 0.6 #两个个体交叉的概率 pm = 0.001; #基因突变的概率 results = [[]] bestindividual = [] bestfit = 0 fitvalue = [] tempop = [[]] pop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1] for i in range(popsize)] for i in range(100): #繁殖100代 objvalue = calobjvalue(pop) #计算目标函数值 fitvalue = calfitvalue(objvalue); #计算个体的适应值 [bestindividual, bestfit] = best(pop, fitvalue) #选出最好的个体和最好的函数值 results.append([bestfit,b2d(bestindividual)]) #每次繁殖，将最好的结果记录下来 selection(pop, fitvalue) #自然选择，淘汰掉一部分适应性低的个体 crossover(pop, pc) #交叉繁殖 mutation(pop, pc) #基因突变 results.sort() print(results[-1]) #打印函数最大值和对应的 def calfitvalue(objvalue):#转化为适应值，目标函数值越大越好，负值淘汰。 fitvalue = [] temp = 0.0 Cmin = 0; for i in range(len(objvalue)): if(objvalue[i] + Cmin > 0): temp = Cmin + objvalue[i] else: temp = 0.0 fitvalue.append(temp) return fitvalue import math def decodechrom(pop): #将种群的二进制基因转化为十进制（0,1023） temp = []; for i in range(len(pop)): t = 0; for j in range(10): t += pop[i][j] * (math.pow(2, j)) temp.append(t) return temp def calobjvalue(pop): #计算目标函数值 temp1 = []; objvalue = []; temp1 = decodechrom(pop) for i in range(len(temp1)): x = temp1[i] * 10 / 1023 #（0,1023）转化为（0,10） objvalue.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x)) return objvalue #目标函数值objvalue[m] 与个体基因 pop[m] 对应 def best(pop, fitvalue): #找出适应函数值中最大值，和对应的个体 px = len(pop) bestindividual = [] bestfit = fitvalue[0] for i in range(1,px): if(fitvalue[i] > bestfit): bestfit = fitvalue[i] bestindividual = pop[i] return [bestindividual, bestfit] import random def sum(fitvalue): total = 0 for i in range(len(fitvalue)): total += fitvalue[i] return total def cumsum(fitvalue): for i in range(len(fitvalue)): t = 0; j = 0; while(j <= i): t += fitvalue[j] j = j + 1 fitvalue[i] = t; def selection(pop, fitvalue): #自然选择（轮盘赌算法） newfitvalue = [] totalfit = sum(fitvalue) for i in range(len(fitvalue)): newfitvalue.append(fitvalue[i] / totalfit) cumsum(newfitvalue) ms = []; poplen = len(pop) for i in range(poplen): ms.append(random.random()) #random float list ms ms.sort() fitin = 0 newin = 0 newpop = pop while newin < poplen: if(ms[newin] < newfitvalue[fitin]): newpop[newin] = pop[fitin]

aimisiyou · 发表于 2018-2-8 12:19:17

本帖最后由 aimisiyou 于 2018-2-8 12:20 编辑

;;;第一步：生成二进制编码个体(染色体数目为n)
(defun ff (n)
(setq lst '((0 5 1)(5 10 0)) vlst nil)
(repeat n
(setq num (fix (rem (getvar "CPUTICKS") 11)))
(setq vlst (cons (car (vl-remove nil (mapcar '(lambda (x) (if (<= (car x) num (cadr x)) (last x) nil)) lst))) vlst))
)
)
_$ (ff 10)
(0 1 0 0 1 1 1 0 0 1)
_$ (ff 15)
(1 0 0 1 0 0 0 0 1 1 1 0 1 0 0)
_$

aimisiyou · 发表于 2018-2-8 12:31:58

;;;第二步：两个个体染色体单点交差
(defun pick (lst i j)
(setq count (length lst) nc 0 picklst nil)
(while (<= nc j)
   (if (<= i nc)
         (setq picklst (cons (nth nc lst) picklst))
   )
   (setq nc (+ nc 1))
)
(reverse picklst)
)
(defun jiaocha (me  fe)
(setq n_dna (length me))
(setq num_point (fix (rem (getvar "CPUTICKS") n_dna)))
(list
      (append (pick me 0 num_point) (pick fe (+ 1 num_point) (- n_dna 1 )))
      (append (pick fe 0 num_point) (pick me (+ 1 num_point) (- n_dna 1 )))
   )
)

_$ (jiaocha '(2 7 8 1 6 5 4) '(3 7 5 4 8 2 9))
((2 7 8 1 8 2 9) (3 7 5 4 6 5 4))
_$ (jiaocha '(2 7 8 1 6 5 4) '(3 7 5 4 8 2 9))
((2 7 5 4 8 2 9) (3 7 8 1 6 5 4))
_$

aimisiyou · 发表于 2018-2-8 12:47:11

;;;第三步：个体单点变异
(defun pick (lst i j)
(setq count (length lst) nc 0 picklst nil)
(while (<= nc j)
   (if (<= i nc)
         (setq picklst (cons (nth nc lst) picklst))
   )
   (setq nc (+ nc 1))
)
(reverse picklst)
)
(defun bianyi (me)
(setq n_dna (length me))
(setq num_point (fix (rem (getvar "CPUTICKS") n_dna)))
(list
      (append (pick me 0 (- num_point 1))
               (list (- 1 (car (pick me num_point num_point))))
               (pick me (+ 1 num_point) (- n_dna 1 ))
      )
)
)

_$ (bianyi '(0 1 1 0 0 1 0 1 0))
((0 1 1 0 0 0 0 1 0))
_$ (bianyi '(0 1 1 0 0 1 0 1 0))
((0 1 1 1 0 1 0 1 0))
_$

aimisiyou · 发表于 2018-2-8 13:22:54

选择算子在遗传算法迭代中将适应度函数引入进来，因为适应度函数式标定一个个体是否足够“好”的重要标准。但是选择过程又不能仅仅完全依赖于适应度函数，因为一个种群中的最优物种并不一定是在全局最优点附近。因此我们也应该给相对来说并那么“好”的个体一点机会让他们繁衍后代, 避免“早熟”。
选择算子在遗传算法迭代中将适应度函数引入进来，因为适应度函数式标定一个个体是否足够“好”的重要标准。但是选择过程又不能仅仅完全依赖于适应度函数，因为一个种群中的最优物种并不一定是在全局最优点附近。因此我们也应该给相对来说并那么“好”的个体一点机会让他们繁衍后代, 避免“早熟”。

aimisiyou · 发表于 2018-2-8 14:42:28

(defun rnd ()
(*(rem (getvar "cputicks") 1e4) 1e-4)
)
(defun rnd_n (n)
(fix (* n (rnd)))
)

aimisiyou · 发表于 2018-2-8 15:01:47

(defun peidui (poplst)
(setq n_pop (length poplst))
(mapcar '(lambda (x y) (list x y)) (pick poplst 0 (/ (- n_pop 2) 2)) (pick poplst (/ n_pop 2) (- n_pop 1)))
)
PEIDUI
_$ (peidui '((1 2)(9 10) (3 5) (6 7) (4 2) (6 8)))
(((1 2) (6 7)) ((9 10) (4 2)) ((3 5) (6 8)))
_$

aimisiyou · 发表于 2018-2-8 15:44:11

;;;来个洗牌算法
(defun xipai (n)
  (setq i 1 j 0 klst nil)
  (while (<= i n)
   (setq klst (cons i klst))
   (setq i (+ 1 i))
)
(while (<= j 20)
      (setq i_pot (rnd_n n))
      (setq j_pot (rnd_n n))
      (setq nmin (min i_pot j_pot))
      (setq nmax (max i_pot j_pot))
      (setq klst (append (pick klst  (+ 1 nmax) (- n 1)) (pick klst (+ 1 nmin) nmax) (pick klst 0 nmin)))
      (setq j (+ j 1))
)
klst
)
XIPAI
_$ (xipai 10)
(6 9 2 8 7 5 10 4 3 1)
_$ (xipai 10)
(8 6 7 3 1 10 9 2 4 5)
_$ (xipai 10)
(7 1 5 10 8 9 2 4 6 3)
_$ (xipai 10)
(10 3 6 5 2 1 7 8 4 9)
_$ (xipai 10)
(2 5 4 7 10 8 6 1 9 3)
_$

账号		自动登录	找回密码
密码			立即注册

[研讨] 遗传算法

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。