遺傳演算法r

1. 遺傳演算法求解背包問題的程序

1樓的不是遺傳演算法吧！
剛好做過這個遺傳演算法解背包問題的論文，給你回答啦~~獨家哦，分數要給偶~~

1、程序開發環境
開發環境：Visual C++6.0 (把Fortran程序改為VC)
操作系統：Windows 2003 Professional
2、程序性能對比
運行時間與加速比（如表1所示）
進程數p（個） 1 2 4
運行時間t（秒） 129s 78s 38s
加速比s 1.65 3.38
表1、運行時間與加速比
3、程序運行結果：
實例數據：
假設物體的重量Weight、物體的收益Profit和背包的容量Contain 分別為：
Weight={ 80，82，85，70，72， 70，66，50，55，25 ，
50，55，40，48，50， 32，22，60，30，32 ，
40，38，35，32，25， 28，30，22，50，30 ，
45，30，60，50，20 ， 65，20，25，30，10 ，
20，25，15，10，10 ， 10，4， 4， 2， 1 }
Profit={ 220，208，198，192，180， 180，165，162，160，158，
155，130，125，122，120 ， 118，115，110，105，101，
100，100，98， 96， 95， 90， 88， 82， 80， 77 ，
75， 73， 72， 70， 69， 66， 65， 63， 60， 58，
56， 50， 30， 20， 15， 10， 8， 5， 3， 1}
Contain=1000，
如何選擇哪些物品裝入該背包可使得在背包的容量約束限制之內所裝物品的總價值最大?
傳統的演算法（動態規劃、遞歸回溯法和貪心演算法所得結果：
總價值為3077 , 總重量為999。
2001年張鈴，張鈸教授在計算機學報上發表的《佳點集遺傳演算法》所得結果
總價值為3103, 總重量為1000。
我們演算法所得結果： 總價值為3103, 總重量為1000。
我們所求得最優解的個體分配情況為：
11010 10111 10110 11011 01111 11101 00001 01001 10000
01000
演算法 最大迭代次數 總價值為 總重量為
傳統的演算法 400 3077 999
佳點集演算法 70 3103 1000
遺傳演算法 75 3103 1000

// knapsack.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <AfxWin.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <conio.h>
#include <stdio.h>

// 重要常量參數
#define popsize 200 //種群的規模
#define pc 0.618 //雜交概率
#define pm 0.03 //變異概率
#define lchrom 50 //染色體長度
#define maxgen 1000 //最大進化代數

struct population
{
unsigned int chrom[lchrom]; //染色體
double weight; //背包重量
double fitness; //適應度
unsigned int parent1,parent2,cross; //雙親、交叉點
};

//新生代種群、父代種群
struct population oldpop[popsize],newpop[popsize];

//背包問題中物體重量、收益、背包容量
int weight[lchrom],profit[lchrom],contain;

//種群的總適應度、最小、最大、平均適應度
double sumfitness,minfitness,maxfitness,avgfitness;

//計算適應度時使用的 懲罰函數系數
double alpha;

//一個種群中最大和最小適應度的個體
int minpop,maxpop;

/* 讀入背包信息,並且計算懲罰函數系數 */
void read_infor()
{
FILE *fp;
int j;

//獲取背包問題信息文件
if ((fp=fopen("knapsack.txt","r"))==NULL)
{
//讀取文件失敗
AfxMessageBox("The file is not found",MB_OK,NULL);
return;
}
//讀入物體收益信息
for (j=0;j<lchrom;j++)
{
fscanf(fp,"%d",&profit[j]);
}
//讀入物體重量信息
for (j=0;j<lchrom;j++)
{
fscanf(fp,"%d",&weight[j]);
}
//讀入背包容量
fscanf(fp,"%d",&contain);
fclose(fp);

}

//根據計算的個體重量,判斷此個體是否該留在群體中
double cal_weight(unsigned int *chr)
{
int j;
double pop_weight;//背包重量

pop_weight=0;
for (j=0;j<lchrom;j++)
{
pop_weight=pop_weight+(*chr)*weight[j];
chr++;
}
return pop_weight;
}

/* 種群中個體適應度計算*/
double cal_fit(unsigned int *chr)
{
int j;
double pop_profit;//適應度

pop_profit=0;
// pop_weight=0;

for (j=0;j<lchrom;j++)
{
pop_profit=pop_profit+(*chr)*profit[j];
// pop_weight=pop_weight+(*chr)*weight[j];
chr++;
}

return pop_profit;
}

/* 群體適應度的最大最小值以及其他信息 */
void statistics(struct population *pop)
{
int i;
double tmp_fit;

sumfitness=pop[0].fitness;
minfitness=pop[0].fitness;
minpop=0;
maxfitness=pop[0].fitness;
maxpop=0;

for (i=1;i<popsize;i++)
{
//計算種群的總適應度
sumfitness=sumfitness+pop[i].fitness;
tmp_fit=pop[i].fitness;
//選擇種群中最大適應度的個體
if ((tmp_fit>maxfitness)&&((int)(tmp_fit*10)%10==0))
{
maxfitness=pop[i].fitness;
maxpop=i;
}

//選擇種群中最小適應度的個體
if (tmp_fit<minfitness)
{
minfitness=pop[i].fitness;
minpop=i;
}

//計算平均適應度
avgfitness=sumfitness/(float)popsize;
}
// printf("\nthe max pop = %d;",maxpop);
// printf("\nthe min pop = %d;",minpop);
// printf("\nthe sumfitness = %f\n",sumfitness);
}

//報告種群信息
void report(struct population *pop,int gen)
{
int j;
int pop_weight=0;

printf("the generation is %d.\n",gen); //輸出種群的代數
//輸出種群中最大適應度個體的染色體信息
printf("The population's chrom is: \n");
for (j=0;j<lchrom;j++)
{
if (j%5==0)
{ printf(" ");}
printf("%1d",pop[maxpop].chrom[j]);
}
//輸出群體中最大適應度
printf("\nThe population's max fitness is %d.",(int)pop[maxpop].fitness);
printf("\nThe knapsack weight is %d.\n\n",(int)pop[maxpop].weight);

}

/* 生成初始種群 */
void initpop()
{
int i,j,ispop;
double tmpWeight;
//變數用於判斷是否為滿足條件的個體
ispop=false;

//生成popsize個種群個體
for(i=0;i<popsize;i++)
{
while (!ispop)
{
for(j=0;j<lchrom;j++)
{
oldpop[i].chrom[j]=rand()%2; //隨機生成個體的染色體
oldpop[i].parent1=0; //雙親
oldpop[i].parent2=0;
oldpop[i].cross=0; //交叉點
}

//選擇重量小於背包容量的個體,即滿足條件
tmpWeight=cal_weight(oldpop[i].chrom);
if (tmpWeight<=contain)
{
oldpop[i].fitness=cal_fit(oldpop[i].chrom);
oldpop[i].weight=tmpWeight;
oldpop[i].parent1=0;
oldpop[i].parent2=0;
oldpop[i].cross=0;
ispop=true;
}
}
//此個體可以加入到種群中
ispop=false;
}
}

/* 遺傳操作 */

//概率選擇試驗
int execise(double probability)
{
double pp;
//如果生成隨機數大於相應的概率則返回真，否則試驗不成功
pp=(double)(rand()%20001/20000.0);
if (pp<=probability) return 1;
return 0;
}

// 選擇進行交叉操作的個體
int selection(int pop)
{
double wheel_pos,rand_Number,partsum;
int parent;

//賭輪法選擇
rand_Number=(rand()%2001)/2000.0;
wheel_pos=rand_Number*sumfitness; //賭輪大小

partsum=0;
parent=0;
do{
partsum=partsum+oldpop[parent].fitness;
parent=parent+1;
} while (partsum<wheel_pos && parent<popsize);
return parent-1;

}

/* 交叉操作 */
int crossover(unsigned int *parent1,unsigned int *parent2,int i)
{
int j,cross_pos;
if (execise(pc))
{
//生成交叉位置0,1,...(lchrom-2)
cross_pos=rand()%(lchrom-1);
}
else cross_pos=lchrom-1;

for (j=0;j<=cross_pos;j++)
{ //保留復制；
//包括在概率選擇不成功時，父體完全保留
newpop[i].chrom[j]=parent1[j];
}
for(j=cross_pos+1;j<=(lchrom-1);j++)
{
//從交叉點開始交叉
newpop[i].chrom[j]=parent2[j];
}

//記錄交叉位置
newpop[i].cross=cross_pos;
return 1;
}

/* 變異操作 */
int mutation(unsigned int alleles)
{
if (execise(pm))
{
if (alleles)
alleles=0;
else alleles=1;
}
//返回變異值，或者返回原值
return alleles;
}

/* 群體更新 */
void generation()
{
unsigned int i,j,mate1,mate2;
double tmpWeight;
int ispop;//記錄是否是符合條件的個體
i=0;
while (i<popsize)
{
ispop=false;
while (!ispop)
{
//選擇
mate1=selection(i);
mate2=selection(i+1);

//交叉
crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,i);

//變異
for (j=0;j<lchrom;j++)
{
newpop[i].chrom[j]=mutation(newpop[i].chrom[j]);
}

//選擇重量小於背包容量的個體,即滿足條件
tmpWeight=cal_weight(newpop[i].chrom);
if (tmpWeight<=contain)
{
newpop[i].fitness=cal_fit(newpop[i].chrom);
newpop[i].weight=tmpWeight;
newpop[i].parent1=mate1;
newpop[i].parent2=mate2;
ispop=true;
}
}
//此個體可以加入到種群中
i=i+1;
}
}

void main(int argc, char* argv[])
{
int gen,oldmaxpop,k;
double oldmax;

read_infor();//讀入背包信息
gen=0;
srand( (unsigned)time( NULL ) );//置隨機種子
initpop();
memcpy(&newpop,&oldpop,popsize*sizeof(struct population));
statistics(newpop);//統計新生種群的信息
report(newpop,gen);
while(gen<maxgen)
{
gen=gen+1;
if (gen%100==0)
{
srand( (unsigned)time( NULL ) );//置隨機種子
}
oldmax=maxfitness;
oldmaxpop=maxpop;
generation();
statistics(newpop); //統計新生代種群信息
//如果新生代種群中個體的最大適應度小於老一代種群
//個體的最大適應度，則保存老一代種群個體的最大適應度
//否則報告新生代的最大適應度
if (maxfitness<oldmax)
{
for(k=0;k<lchrom;k++)
newpop[minpop].chrom[k]=oldpop[oldmaxpop].chrom[k];
newpop[minpop].fitness=oldpop[oldmaxpop].fitness;
newpop[minpop].parent1=oldpop[oldmaxpop].parent1;
newpop[minpop].parent2=oldpop[oldmaxpop].parent2;
newpop[minpop].cross=oldpop[oldmaxpop].cross;
statistics(newpop);
}
else if (maxfitness>oldmax)
{
report(newpop,gen);
}

//保存新生代種群的信息到老一代種群信息空間
memcpy(&oldpop,&newpop,popsize*sizeof(struct population));
}

printf("It is over.");
getch();
}

2. r軟體，rbga，可以做多個目標函數的遺傳演算法嗎

遺傳演算法的操作使用適者生存的原則，在潛在的種群中逐次產生一個近似最優解的方案，在每一代中，根據個體在問題域中的適應度值和從自然遺傳學中借鑒來的再造方法進行個體選擇，產生一個新的近似解。這個過程會導致種群中個體的進化，得到的新個體比原來個體更能適應環境，就像自然界中的改造一樣。
如果從生物進化的角度，我們可以這樣理解。在一個種群中，個體數量已經有一定規模，為了進化發展，通過選擇和繁殖產生下一代的個體，其中繁殖過程包括交配和突變。根據適者生存的原則，選擇過程會根據新個體的適應度進行保留或淘汰，但也不是完全以適應度高低作為導向，如果單純選擇適應度高的個體可能會產生局部最優的種群，而非全局最優，這個種群將不會再進化，稱為早熟。之後，通過繁殖過程，讓個體兩兩交配產生下一代新個體，上一代個體中優秀的基因會保留給下一代，而劣制的基因將被個體另一半的基因所代替。最後，通過小概率事件發生基因突變，通過突變產生新的下一代個體，實現種群的變異進化。
經過這一系列的選擇、交配和突變的過程，產生的新一代個體將不同於初始的一代，並一代一代向增加整體適應度的方向發展，因為最好的個體總是更多的被選擇去產生下一代，而適應度低的個體逐漸被淘汰掉。這樣的過程不斷的重復：每個個體被評價，計算出適應度，兩個個體交配，然後突變，產生第三代。周而復始，直到終止條件滿足為止。

3. matlab遺傳演算法求最小包容圓

首先定義優化目標函數：

functionr=rmax(p,x)

%p：已知平面點集。p的每一列就是一點的xy坐標。

%x：包絡圓的中心坐標。

a=x(1);b=x(2);

r=max(((p(1,:)-a).^2+(p(2,:)-b).^2).^0.5);

易知，當r取值最小時，即為最小包絡圓。

下面是matlab求解程序：

p=rand(2,10);%已知平面點列。p的每一列就是一點的xy坐標。

lb=min(p')';%

ub=max(p')';%限定包絡圓的中心范圍。

options=gaoptimset('TimeLimit',150);%設定求解時間

[xfvalexit]=ga(@(x)rmax(p,x),2,[],[],[],[],lb,ub,[],options);%x就是包絡圓中心的橫縱坐標。

運行圖：

4. matlab用遺傳演算法解決TSP的問題，求幫助

把下面的（1）-（7）依次存成相應的.m文件，在（7）的m文件下運行就可以了
（1） 適應度函數fit.m
function fitness=fit(len,m,maxlen,minlen)
fitness=len;
for i=1:length(len)
fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.0001)).^m;
end
(2)個體距離計算函數 mylength.m
function len=myLength(D,p)
[N,NN]=size(D);
len=D(p(1,N),p(1,1));
for i=1:(N-1)
len=len+D(p(1,i),p(1,i+1));
end

end
(3)交叉操作函數 cross.m
function [A,B]=cross(A,B)
L=length(A);
if L<10
W=L;
elseif ((L/10)-floor(L/10))>=rand&&L>10
W=ceil(L/10)+8;
else
W=floor(L/10)+8;
end
p=unidrnd(L-W+1);
fprintf('p=%d ',p);
for i=1:W
x=find(A==B(1,p+i-1));
y=find(B==A(1,p+i-1));
[A(1,p+i-1),B(1,p+i-1)]=exchange(A(1,p+i-1),B(1,p+i-1));
[A(1,x),B(1,y)]=exchange(A(1,x),B(1,y));
end

end
(4)對調函數 exchange.m
function [x,y]=exchange(x,y)
temp=x;
x=y;
y=temp;

end
(5)變異函數 Mutation.m
function a=Mutation(A)
index1=0;index2=0;
nnper=randperm(size(A,2));
index1=nnper(1);
index2=nnper(2);
%fprintf('index1=%d ',index1);
%fprintf('index2=%d ',index2);

temp=0;
temp=A(index1);
A(index1)=A(index2);
A(index2)=temp;
a=A;
end
(6)連點畫圖函數 plot_route.m
function plot_route(a,R)
scatter(a(:,1),a(:,2),'rx');
hold on;
plot([a(R(1),1),a(R(length(R)),1)],[a(R(1),2),a(R(length(R)),2)]);
hold on;
for i=2:length(R)
x0=a(R(i-1),1);
y0=a(R(i-1),2);
x1=a(R(i),1);
y1=a(R(i),2);
xx=[x0,x1];
yy=[y0,y1];
plot(xx,yy);
hold on;
end

end
(7)主函數
clear;
clc;
%%%%%%%%%%%%%%%輸入參數%%%%%%%%
N=50; %%城市的個數
M=100; %%種群的個數
C=100; %%迭代次數
C_old=C;
m=2; %%適應值歸一化淘汰加速指數
Pc=0.4; %%交叉概率
Pmutation=0.2; %%變異概率
%%生成城市的坐標
pos=randn(N,2);
%%生成城市之間距離矩陣
D=zeros(N,N);
for i=1:N
for j=i+1:N
dis=(pos(i,1)-pos(j,1)).^2+(pos(i,2)-pos(j,2)).^2;
D(i,j)=dis^(0.5);
D(j,i)=D(i,j);
end
end
%%如果城市之間的距離矩陣已知，可以在下面賦值給D，否則就隨機生成

%%生成初始群體
popm=zeros(M,N);
for i=1:M
popm(i,:)=randperm(N);
end
%%隨機選擇一個種群
R=popm(1,:);

figure(1);
scatter(pos(:,1),pos(:,2),'rx');
axis([-3 3 -3 3]);
figure(2);
plot_route(pos,R); %%畫出種群各城市之間的連線
axis([-3 3 -3 3]);
%%初始化種群及其適應函數
fitness=zeros(M,1);
len=zeros(M,1);
for i=1:M
len(i,1)=myLength(D,popm(i,:));
end
maxlen=max(len);
minlen=min(len);
fitness=fit(len,m,maxlen,minlen);
rr=find(len==minlen);
R=popm(rr(1,1),:);
for i=1:N
fprintf('%d ',R(i));
end
fprintf('\n');
fitness=fitness/sum(fitness);

distance_min=zeros(C+1,1); %%各次迭代的最小的種群的距離
while C>=0
fprintf('迭代第%d次\n',C);
%%選擇操作
nn=0;
for i=1:size(popm,1)
len_1(i,1)=myLength(D,popm(i,:));
jc=rand*0.3;
for j=1:size(popm,1)
if fitness(j,1)>=jc
nn=nn+1;
popm_sel(nn,:)=popm(j,:);
break;
end
end
end
%%每次選擇都保存最優的種群
popm_sel=popm_sel(1:nn,:);
[len_m len_index]=min(len_1);
popm_sel=[popm_sel;popm(len_index,:)];

%%交叉操作
nnper=randperm(nn);
A=popm_sel(nnper(1),:);
B=popm_sel(nnper(2),:);
for i=1:nn*Pc
[A,B]=cross(A,B);
popm_sel(nnper(1),:)=A;
popm_sel(nnper(2),:)=B;
end
%%變異操作
for i=1:nn
pick=rand;
while pick==0
pick=rand;
end
if pick<=Pmutation
popm_sel(i,:)=Mutation(popm_sel(i,:));
end
end
%%求適應度函數
NN=size(popm_sel,1);
len=zeros(NN,1);
for i=1:NN
len(i,1)=myLength(D,popm_sel(i,:));
end
maxlen=max(len);
minlen=min(len);
distance_min(C+1,1)=minlen;
fitness=fit(len,m,maxlen,minlen);
rr=find(len==minlen);
fprintf('minlen=%d\n',minlen);
R=popm_sel(rr(1,1),:);
for i=1:N
fprintf('%d ',R(i));
end
fprintf('\n');
popm=[];
popm=popm_sel;
C=C-1;
%pause(1);
end
figure(3)
plot_route(pos,R);
axis([-3 3 -3 3]);