注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Bioinformatics home

 
 
 

日志

 
 

Perl 版的旅行商问题--遗传算法  

2012-06-04 22:38:08|  分类: 生物信息编程 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
use Data::Struct; 
use strict;
use warnings;
struct Group => [ qw(path cost) ];

my $num_C=shift; #define num_C  10   //城市个数
my $N=shift;#define N      100  //群体规模为100
my $pc=shift;#define pc     0.9  //交叉概率为0.9
my $pm=shift;#define pm     0.1  //变异概率为10%
my $ps=shift;#define ps     0.6  //进行选择时保留的比例
my $genmax=shift;#define genmax 200  //最大代数200


$num_C=10; #define num_C  10   //城市个数
$N=100;#define N      100  //群体规模为100
$pc=0.9;#define pc     0.9  //交叉概率为0.9
$pm=0.1;#define pm     0.1  //变异概率为10%
$ps=0.6;#define ps     0.6  //进行选择时保留的比例
$genmax=1000;#define genmax 200  //最大代数200
 
# /***************************************************************************/
# /* 城市间的距离信息:                                                      */
# /*           北京  天津  武汉  深圳  长沙  成都  杭州  西安  拉萨  南昌    */
# /*           (0)   (1)   (2)   (3)   (4)   (5)   (6)   (7)   (8)   (9)     */
# /*  北京(0)   0    118   1272  2567  1653  2097  1425  1177  3947  1574    */
# /*  天津(1)  118    0    1253  2511  1633  2077  1369  1157  3961  1518    */
# /*  武汉(2)  1272  1253   0    1462  380   1490  821   856   3660  385     */
# /*  深圳(3)  2567  2511  1462   0    922   2335  1562  2165  3995  933     */
# /*  长沙(4)  1653  1633  380   922    0    1700  1041  1135  3870  456     */
# /*  成都(5)  2097  2077  1490  2335  1700   0    2311  920   2170  1920    */
# /*  杭州(6)  1425  1369  821   1562  1041  2311   0    1420  4290  626     */
# /*  西安(7)  1177  1157  856   2165  1135  920   1420   0    2870  1290    */
# /*  拉萨(8)  3947  3961  3660  3995  3870  2170  4290  2870   0    4090    */
# /*  南昌(9)  1574  1518  385   993   456   1920  626   1290  4090   0      */
# /***************************************************************************/
#第 1200 代,个体 99 :3  4  2  9  6  1  0  7  5  8    代价值为:8067 



my $num_gen=0;        #//记录当前达到第几代
my @Cost_table=([0,118,1272,2567,1653,2097,1425,1177,3947,1574],
[118,0,1253,2511,1633,2077,1369,1157,3961,1518],
[1272,1253,0,1462,380,1490,821,856,3660,385],
[2567,2511,1462,0,922,2335,1562,2165,3995,933],
[1653,1633,380,922,0,1700,1041,1135,3870,456],
[2097,2077,1490,2335,1700,0,2311,920,2170,1920],
[1425,1369,821,1562,1041,2311,0,1420,4290,626],
[1177,1157,856,2165,1135,920,1420,0,2870,1290],
[3947,3961,3660,3995,3870,2170,4290,2870,0,4090],
[1574,1518,385,993,456,1920,626,1290,4090,0]);
  my @groups;
  my $i;
  my $temp;
  foreach $i(1..$N)
  {
    $temp =struct Group => { path => [], cost => '' };
push @groups,$temp;
  }
  Initial_gen(\@groups);     #//初始化种群
  Evolution(\@groups);       #//进化:选择、交叉、变异 
 
#/* 初始化种群 */
#sub Initial_gen(struct unit group[N])
sub Initial_gen 
{
  my $groups=shift;
  my $N=scalar(@$groups);
  my($i,$j,$k);
  #struct unit *p;
  for($i=0;$i<=$N-1;$i++) #//初始化种群里的100个个体
{
 my $p=$$groups[$i];#p=&group[i]; //p指向种群的第i个个体
 
   for($j=0;$j<=$num_C-1;$j++) #//生成10个城市间的一个随机路径
{
 $k=0;
 if($j==0)
 {  
    ${$p->path}[$j]=RandomInteger(0,$num_C-1);
 }
 else
{
 ${$p->path}[$j]=RandomInteger(0,$num_C-1);
 while($k<$j)
{
 #//与之前城市重复,重新生成一个城市
 if(${$p->path}[$j]==${$p->path}[$k])
 {
  ${$p->path}[$j]=RandomInteger(0,$num_C-1); 
  $k=0; 
 }
 else 
 {
 $k++;
 }
}#//end while
}
}#//end 生成路径
 Calculate_cost($p);# //计算该路径的代价值
}#//end 初始化种群
}

#/* 计算某个路径的代价值 */
#void Calculate_cost(struct unit *p) 
sub Calculate_cost #(struct unit *p)
{
  my $p=shift;
  my $j;
  $p->cost=0;
  for($j=1;$j<=$num_C-1;$j++)
  { 
 $p->cost+= $Cost_table[${$p->path}[$j-1]][${$p->path}[$j]];
  }
  #$p->cost+=$Cost_table[${$p->path}[$num_C-1]][${$p->path}[0]]; #所有地址均从南昌出发
}


#/* 生成一个介于两整型数之间的随机整数 */
sub RandomInteger
{
my $low=shift;
my $high=shift;
my $k;
my $d;
# my $RAND_MAX= 2 ** 63; # $RAND_MAX是perl中可表示的最大整型数
# $k=rand();
# $k=($k!=$RAND_MAX)?$k:($k-1); 
# $d=$k /$RAND_MAX;
# $k=int($d*($high-$low+1));
 
return int( rand( $high - $low +1)) + $low;
#return ($low+$k);
}



#/* 将种群中个体按代价从小到大排序 */void Sort(struct unit group[N])
sub Sort
{
  my $groups=shift;
  my ($i,$j);
  #struct unit temp,*p1,*p2;
  my $N=scalar(@$groups);
  my ($temp,$p1,$p2);
  $temp =struct Group => { path => [], cost => '' };
  for($j=1;$j<=$N-1;$j++) #//排序总共需进行N-1轮
{
 for($i=1;$i<=$N-1;$i++)
{
 $p1=$$groups[$i-1]; #=&group[i-1]; 
 $p2=$$groups[$i]; #p2=&group[i];
 if($p1->cost > $p2->cost) #//代价值大的往后排
{
 Copy_unit($p1,$temp);
 Copy_unit($p2,$p1);
 Copy_unit($temp,$p2);
}#//end if
}#//end 一轮排序
}#//end 排序  
}

#/* 复制种群中的p1到p2中 */
#void Copy_unit(struct unit *p1,struct unit *p2)
sub Copy_unit 
{
my $p1=shift;
my $p2=shift;
my $i;
for($i=0;$i<=$num_C-1;$i++) 
{
${$p2->path}[$i]=${$p1->path}[$i]; #p2->path[i]=p1->path[i]
}
$p2->cost=$p1->cost;
}

#/* 检查k是否在son[num_C]中已出现过 */
#int search_son(int son[num_C],int k)
sub search_son #(int son[num_C],int k)
{
  my $son=shift;
  my $k=shift;
  my $i;
  for($i=0;$i<=$num_C-1;$i++)
  {
 if($$son[$i]==$k) 
 {
   return -1
 }
  }
  return 1;
}

#/* 交叉 */
#void Cross(struct unit *p1,struct unit *p2)
sub Cross #(struct unit *p1,struct unit *p2)
{
  my $p1=shift;
  my $p2=shift;
  my ($i,$j,$cross_point);
  my  (@son1,@son2);
  for($i=0;$i<=$num_C-1;$i++)# //初始化son1、son2
{
 $son1[$i]=-1;
 $son2[$i]=-1;
}
  $cross_point=RandomInteger(1,$num_C-1);# //交叉位随机生成
 # //交叉,生成子代
 # //子代1
  #//子代1前半部分直接从父代复制
  for($i=0;$i<=$cross_point-1;$i++)  
  {
    $son1[$i]=${$p1->path}[$i];
  }
  for($i=$cross_point;$i<=$num_C-1;$i++)
{
 for($j=0;$j<=$num_C-1;$j++) #//补全p1
{
 if(search_son(\@son1,${$p2->path}[$j])==1)
$son1[$i]=${$p2->path}[$j]; 
last;
}
}
}#//end 子代1
  #//子代2
  #//子代1后半部分直接从父代复制
  for($i=$cross_point;$i<=$num_C-1;$i++)  
  {
     $son2[$i]=${$p2->path}[$i];
  }
  for($i=0;$i<=$cross_point-1;$i++)
{
 for($j=0;$j<=$num_C-1;$j++)# //补全p2
{
 if(search_son(\@son2,${$p1->path}[$j])==1)
{ $son2[$i]=${$p1->path}[$j]; last; }

}
}#//end 子代2
  #//end 交叉
  for($i=0;$i<=$num_C-1;$i++)
{
 ${$p1->path}[$i]=$son1[$i];
 ${$p2->path}[$i]=$son2[$i];
}
  Calculate_cost($p1); #//计算子代p1的代价
  Calculate_cost($p2); #//计算子代p2的代价
}


#void Varation(struct unit group[N],int i);
sub Varation #(struct unit group[N],int flag_v)
{
  my $groups=shift;
  my $flag_v=shift;
#struct unit temp,*p1,*p2;
  my $N=scalar(@$groups);
  my( $flag,$i,$j,$k,$temp);
  my $p;
 
  $flag=RandomInteger(1,100);
  # //在进化后期,增大变异概率
  if($flag<=(($flag_v>100)?(5*100*$pm):(100*$pm)))
{
 $i=RandomInteger(0,$N-1);    #   //确定发生变异的个体
 $j=RandomInteger(0,$num_C-1); # //确定发生变异的位
 $k=RandomInteger(0,$num_C-1);
 $p=$$groups[$i];                # //变异
 $temp=${$p->path}[$j];
 ${$p->path}[$j]=${$p->path}[$k];
 ${$p->path}[$k]=$temp;
 Calculate_cost($p);           #//重新计算变异后路径的代价
}
}



#/* 种群进化,进化代数由genmax决定 */
#void Evolution(struct unit group[N])
sub Evolution
{
  my $groups=shift;
  #struct unit temp,*p1,*p2;
  my $N=scalar(@$groups);
  
  my ($i,$j);
  my ($temp1,$temp2,$temp3,$temp4,$temp5);
  $temp1=$N*$pc/2;
  $temp2=$N*(1-$pc);
  $temp3=$N*(1-$pc/2);
  $temp4=$N*(1-$ps);
  $temp5=$N*$ps;
  for($i=1;$i<=$genmax;$i++)
{
# //选择
      Sort($groups);
 Print_optimum($groups,$i-1); #//输出当代(第i-1代)种群
      for($j=0;$j<=$temp4-1;$j++)
{ Copy_unit($groups[$j],$groups[$j+$temp5]); }
 #//交叉
 for($j=0;$j<=$temp1-1;)
{
 Cross($groups[$temp2+$j],$groups[$temp3+$j]);
 $j+=2;
}
 #//变异
 Varation($groups,$i);
}
  Sort($groups);
  Print_optimum($groups,$i-1); #//输出当代(第i-1代)种群
}


 
#/* 输出当代种群中的每个个体 */
#void Print_optimum(struct unit group[N],int k)
sub Print_optimum #(struct unit group[N],int k)
{
  my ($i,$j);
  my $groups=shift;
  my $k=shift;
  #struct unit temp,*p1,*p2;
  my $N=scalar(@$groups);
  
  #struct unit *p;
  my $p;
  print "当前第 $k 代:\n";
  for($i=0;$i<=$N-1;$i++)
{
 print "第 $k 代,个体 $i :" ;
 $p=$$groups[$i];
 for($j=0;$j<=$num_C-1;$j++)  
 {
  print ${$p->path}[$j]."  ";
 } 
 print "  代价值为:".$p->cost." \n" ;
}
}

 
  评论这张
 
阅读(551)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017