GreenSimJ原创GreenSimJ原创遗传算法解决车辆路径

1、GreenSim.J原创】GreenSim.J原创】遗传算法解决车辆路径问题（VRP）(2007-08-29 11:22:12) 标签：知识/探索 关于遗传算法博客里已经很多了，这次贴个c的代码，下面的源代码是解决车辆路径问题的。谈一点经验性的东西，就是在进行染色体交叉时，一定要注意基因结构的问题。根据具体应用情况，尽量要保证好的基因结构遗传到后代中。其实此时的交叉变异等所有的操作，考虑的是基因结构，而不是单个的基因。所以在设计编码方式时就要考虑到设计出良好的基因结构。便于分割和组合的结构是好的设计。 部分源程序：（/* 最优化函数 */void GAOptim( float *vData,

2、float vP, int vGenNum, int *pBestGen ) int vFlockSize = FLOCKSIZE ; int GENNUM = vGenNum ; float P = vP ; int vLen = LEN ; int MotherFlockFLOCKSIZELEN ; int FatherFlockFLOCKSIZELEN ; int ChildFlock2*FLOCKSIZELEN ; int mBestGenLEN ; int mCounter, mCounter1 ; int *pTemp1; /产生初始种群 for( mCounter1 = 0 ;

3、mCounter1<FLOCKSIZE ; mCounter1+ ) pTemp1 = MotherFlockmCounter1 ; PermutRnd( LEN , 1 , pTemp1 ) ; for( mCounter1 = 0 ; mCounter1<FLOCKSIZE ; mCounter1+ ) pTemp1 = FatherFlockmCounter1 ; PermutRnd( LEN , 1 , pTemp1 ) ; PermutRnd( LEN , 1 , mBestGen ) ; / 初始化最优种群 for( mCounter = 0 ; mCounter &l

4、t; GENNUM ; mCounter+ ) /交叉 GenCross( MotherFlock,FatherFlock,ChildFlock,vData ) ; /遗传 GenHeri( MotherFlock,FatherFlock,ChildFlock,mBestGen,vData ) ; /变异 GenAber( MotherFlock,FatherFlock,mBestGen,vP,vData ) ; for( mCounter = 0 ; mCounter < vLen ; mCounter+ ) *( pBestGen + mCounter ) = mBestGenmCo

5、unter ; return ; /* 交叉子函数 */void GenCross( int *MotherFlock, int *FatherFlock,int *ChildFlock, float *vData ) int mCounter, mCounter1, mCounter2, mCounter3 ; int mIndex = 0 ; int mCrossLen1 = 0 , mCrossLen2 = 0 ; int mCrossFlag = 0 ; int mMoFkTemp1LEN, mMoFkTemp2LEN, mFaFkTemp1LEN, mFaFkTemp2LEN ; i

6、nt mMotherFlockFLOCKSIZELEN , mFatherFlockFLOCKSIZELEN ; int mChildFlock2*FLOCKSIZELEN ; int mIndex1LEN, mIndex2LEN ; int *pMo, *pFa, *pChid ; pMo = mMotherFlock0 ; pFa = mFatherFlock0; pChid = mChildFlock0 ; for(mCounter = 0 ; mCounter<FLOCKSIZE*LEN ; mCounter+) *( pMo + mCounter ) = *( MotherFl

7、ock + mCounter ) ; *( pFa + mCounter ) = *( FatherFlock + mCounter ) ; for( mCounter = 0 ; mCounter<FLOCKSIZE ; mCounter+ ) /* 进行双亲双子交叉 */ / 产生交叉点 mIndex = floor( UniRnd()*LEN ) ; / 根据交叉点，寻找两段合适的遗传序列 for( mCounter1 = 0 ; mCounter1<LEN ; mCounter1+ ) / 数组初始化 mMoFkTemp1mCounter1 = 0 ; mMoFkTemp2

8、mCounter1 = 0 ; mFaFkTemp1mCounter1 = 0 ; mFaFkTemp2mCounter1 = 0 ; / 存储四段序列 for( mCounter1 = 0,mCounter2 = 0,mCounter3 = 0 ; mCounter1<LEN ; mCounter1+ ) if(mCounter1<mIndex) mMoFkTemp1mCounter2 = mMotherFlockmCountermCounter1 ; mFaFkTemp1mCounter2 = mFatherFlockmCountermCounter1 ; mCounter2+

9、 ; else mMoFkTemp2mCounter3 = mMotherFlockmCountermCounter1 ; mFaFkTemp2mCounter3 = mFatherFlockmCountermCounter1 ; mCounter3+ ; mCrossLen1 = mIndex - 1 ; mCrossLen2 = LEN - mCrossLen1 ; / 将两段好的序列放在mMoFkTemp1,mMoFkTemp2中，差的放在mFaFkTemp1,mFaFkTemp2中 mCrossFlag = BestChip(mMoFkTemp1,mMoFkTemp2,mFaFkTem

10、p1,mFaFkTemp2,mCrossLen1,mCrossLen2,vData) ; / 根据两段序列构造完整基因，存放在子代中 PermutRnd( mCrossLen1 , 1 , mIndex1 ) ; / 产生补充基因的随机数 PermutRnd( mCrossLen2 , 1 , mIndex2 ) ; for( mCounter1 = 0, mCounter2 = 0 ; mCounter1<LEN ; mCounter1+ ) if(mCounter1<=mCrossLen1) mChildFlock2*mCountermCounter1 = mMoFkTemp1

11、mCounter1 ; if(mCrossFlag=1) /如果交叉成功,则补充基因,否则直接复制到子代 mChildFlock2*mCounter+1mCounter1 = mFaFkTemp1 mIndex1mCounter1 ; else mChildFlock2*mCounter+1mCounter1 = mFaFkTemp1mCounter1 ; else mChildFlock2*mCountermCounter1 = mMoFkTemp2mCounter2 ; if(mCrossFlag=1) mChildFlock2*mCounter+1mCounter1 = mFaFkTem

12、p2 mIndex2mCounter2 ; else mChildFlock2*mCounter+1mCounter1 = mFaFkTemp2mCounter2 ; mCounter2+ ; / 最后把产生的子代转入到输入参数ChildFlock中 for ( mCounter = 0 ; mCounter<2*FLOCKSIZE*LEN ; mCounter+ ) *( ChildFlock+mCounter ) = *( pChid+mCounter ) ; / 子函数，将输入的四段基因中最好的两段存放在mMoFkTemp1和mMoFkTemp2中 / 返回交叉信息，返回1为交叉，

13、返回-1为没交叉 int BestChip( int *mMoFkTemp1, int *mMoFkTemp2, int *mFaFkTemp1, int *mFaFkTemp2, int mCrossLen1, int mCrossLen2, float *mData ) int vFlag = 0, vCounter1; int vTemp1 ; int vLen ; int FLAG = -1 ; vLen = mCrossLen1 + mCrossLen2 ; / 判断前一部分序列的特性并存储好的序列 vFlag = BestJudger(mMoFkTemp1,mFaFkTemp1,m

14、CrossLen1,mData,vLen ); if(vFlag=2) for( vCounter1 = 0 ; vCounter1<mCrossLen1 ; vCounter1+ ) vTemp1 = *(mMoFkTemp1+vCounter1) ; *(mMoFkTemp1+vCounter1) = *(mFaFkTemp1+vCounter1) ; *(mFaFkTemp1+vCounter1) = vTemp1 ; FLAG = 1 ; / 判断后一部分序列的特性并存储好的序列 vFlag = BestJudger(mMoFkTemp2,mFaFkTemp2,mCrossLen

15、2,mData,vLen ); if(vFlag=2) for( vCounter1 = 0 ; vCounter1<mCrossLen2 ; vCounter1+ ) vTemp1 = *(mMoFkTemp2+vCounter1) ; *(mMoFkTemp2+vCounter1) = *(mFaFkTemp2+vCounter1) ; *(mFaFkTemp2+vCounter1) = vTemp1 ; FLAG = -1*FLAG ; return(FLAG) ; /* 变异子函数 */void GenAber( int *MotherFlock,int *FatherFlock

16、, int *BestGen, float P, float *mData) int mCounter, mCounter1, mCounter2 ; int mIndexLEN ; int mTemp1 = 0; for( mCounter = 0 ; mCounter<LEN ; mCounter+ ) if( P>UniRnd() ) /当满足变异概率时进行变异母代 PermutRnd( LEN , 1 , mIndex ) ; mTemp1 = *(MotherFlock+mCounter*LEN+mIndex1) ; *(MotherFlock+mCounter*LEN+

17、mIndex1) = *(MotherFlock+mCounter*LEN+mIndex2) ; *(MotherFlock+mCounter*LEN+mIndex2) = mTemp1 ; mTemp1 = *(MotherFlock+mCounter*LEN+mIndex3) ; *(MotherFlock+mCounter*LEN+mIndex3) = *(MotherFlock+mCounter*LEN+mIndex4) ; *(MotherFlock+mCounter*LEN+mIndex4) = mTemp1 ; if( P>UniRnd() ) /当满足变异概率时进行变异父

18、代 PermutRnd( LEN , 1 , mIndex ) ; mTemp1 = *(FatherFlock+mCounter*LEN+mIndex1) ; *(FatherFlock+mCounter*LEN+mIndex1) = *(FatherFlock+mCounter*LEN+mIndex2) ; *(FatherFlock+mCounter*LEN+mIndex2) = mTemp1 ; mTemp1 = *(FatherFlock+mCounter*LEN+mIndex3) ; *(FatherFlock+mCounter*LEN+mIndex3) = *(FatherFlo

19、ck+mCounter*LEN+mIndex4) ; *(FatherFlock+mCounter*LEN+mIndex4) = mTemp1 ; /保存最好的序列 mTemp1 = BestJudger(BestGen, MotherFlock, LEN, mData, LEN ) ; if( mTemp1 = 2 ) for( mCounter=0;mCounter<LEN;mCounter+ ) *(BestGen+mCounter) = *(MotherFlock+mCounter) ; else for( mCounter=0;mCounter<LEN;mCounter+

20、 ) *(MotherFlock+mCounter) = *(BestGen+mCounter) ; 更多问题请联系我们（VRP）(2007-08-29 11:22:12) 关于遗传算法博客里已经很多了，这次贴个c的代码，下面的源代码是解决车辆路径问题的。谈一点经验性的东西，就是在进行染色体交叉时，一定要注意基因结构的问题。根据具体应用情况，尽量要保证好的基因结构遗传到后代中。其实此时的交叉变异等所有的操作，考虑的是基因结构，而不是单个的基因。所以在设计编码方式时就要考虑到设计出良好的基因结构。便于分割和组合的结构是好的设计。 部分源程序：（/* 最优化函数 */void GAOptim( f

21、loat *vData, float vP, int vGenNum, int *pBestGen ) int vFlockSize = FLOCKSIZE ; int GENNUM = vGenNum ; float P = vP ; int vLen = LEN ; int MotherFlockFLOCKSIZELEN ; int FatherFlockFLOCKSIZELEN ; int ChildFlock2*FLOCKSIZELEN ; int mBestGenLEN ; int mCounter, mCounter1 ; int *pTemp1; /产生初始种群 for( mCo

22、unter1 = 0 ; mCounter1<FLOCKSIZE ; mCounter1+ ) pTemp1 = MotherFlockmCounter1 ; PermutRnd( LEN , 1 , pTemp1 ) ; for( mCounter1 = 0 ; mCounter1<FLOCKSIZE ; mCounter1+ ) pTemp1 = FatherFlockmCounter1 ; PermutRnd( LEN , 1 , pTemp1 ) ; PermutRnd( LEN , 1 , mBestGen ) ; / 初始化最优种群 for( mCounter = 0

23、; mCounter < GENNUM ; mCounter+ ) /交叉 GenCross( MotherFlock,FatherFlock,ChildFlock,vData ) ; /遗传 GenHeri( MotherFlock,FatherFlock,ChildFlock,mBestGen,vData ) ; /变异 GenAber( MotherFlock,FatherFlock,mBestGen,vP,vData ) ; for( mCounter = 0 ; mCounter < vLen ; mCounter+ ) *( pBestGen + mCounter )

24、= mBestGenmCounter ; return ; /* 交叉子函数 */void GenCross( int *MotherFlock, int *FatherFlock,int *ChildFlock, float *vData ) int mCounter, mCounter1, mCounter2, mCounter3 ; int mIndex = 0 ; int mCrossLen1 = 0 , mCrossLen2 = 0 ; int mCrossFlag = 0 ; int mMoFkTemp1LEN, mMoFkTemp2LEN, mFaFkTemp1LEN, mFaF

25、kTemp2LEN ; int mMotherFlockFLOCKSIZELEN , mFatherFlockFLOCKSIZELEN ; int mChildFlock2*FLOCKSIZELEN ; int mIndex1LEN, mIndex2LEN ; int *pMo, *pFa, *pChid ; pMo = mMotherFlock0 ; pFa = mFatherFlock0; pChid = mChildFlock0 ; for(mCounter = 0 ; mCounter<FLOCKSIZE*LEN ; mCounter+) *( pMo + mCounter )

26、= *( MotherFlock + mCounter ) ; *( pFa + mCounter ) = *( FatherFlock + mCounter ) ; for( mCounter = 0 ; mCounter<FLOCKSIZE ; mCounter+ ) /* 进行双亲双子交叉 */ / 产生交叉点 mIndex = floor( UniRnd()*LEN ) ; / 根据交叉点，寻找两段合适的遗传序列 for( mCounter1 = 0 ; mCounter1<LEN ; mCounter1+ ) / 数组初始化 mMoFkTemp1mCounter1 = 0

27、 ; mMoFkTemp2mCounter1 = 0 ; mFaFkTemp1mCounter1 = 0 ; mFaFkTemp2mCounter1 = 0 ; / 存储四段序列 for( mCounter1 = 0,mCounter2 = 0,mCounter3 = 0 ; mCounter1<LEN ; mCounter1+ ) if(mCounter1<mIndex) mMoFkTemp1mCounter2 = mMotherFlockmCountermCounter1 ; mFaFkTemp1mCounter2 = mFatherFlockmCountermCounter1

28、 ; mCounter2+ ; else mMoFkTemp2mCounter3 = mMotherFlockmCountermCounter1 ; mFaFkTemp2mCounter3 = mFatherFlockmCountermCounter1 ; mCounter3+ ; mCrossLen1 = mIndex - 1 ; mCrossLen2 = LEN - mCrossLen1 ; / 将两段好的序列放在mMoFkTemp1,mMoFkTemp2中，差的放在mFaFkTemp1,mFaFkTemp2中 mCrossFlag = BestChip(mMoFkTemp1,mMoFkT

29、emp2,mFaFkTemp1,mFaFkTemp2,mCrossLen1,mCrossLen2,vData) ; / 根据两段序列构造完整基因，存放在子代中 PermutRnd( mCrossLen1 , 1 , mIndex1 ) ; / 产生补充基因的随机数 PermutRnd( mCrossLen2 , 1 , mIndex2 ) ; for( mCounter1 = 0, mCounter2 = 0 ; mCounter1<LEN ; mCounter1+ ) if(mCounter1<=mCrossLen1) mChildFlock2*mCountermCounter1

30、 = mMoFkTemp1mCounter1 ; if(mCrossFlag=1) /如果交叉成功,则补充基因,否则直接复制到子代 mChildFlock2*mCounter+1mCounter1 = mFaFkTemp1 mIndex1mCounter1 ; else mChildFlock2*mCounter+1mCounter1 = mFaFkTemp1mCounter1 ; else mChildFlock2*mCountermCounter1 = mMoFkTemp2mCounter2 ; if(mCrossFlag=1) mChildFlock2*mCounter+1mCounte

31、r1 = mFaFkTemp2 mIndex2mCounter2 ; else mChildFlock2*mCounter+1mCounter1 = mFaFkTemp2mCounter2 ; mCounter2+ ; / 最后把产生的子代转入到输入参数ChildFlock中 for ( mCounter = 0 ; mCounter<2*FLOCKSIZE*LEN ; mCounter+ ) *( ChildFlock+mCounter ) = *( pChid+mCounter ) ; / 子函数，将输入的四段基因中最好的两段存放在mMoFkTemp1和mMoFkTemp2中 / 返

32、回交叉信息，返回1为交叉，返回-1为没交叉 int BestChip( int *mMoFkTemp1, int *mMoFkTemp2, int *mFaFkTemp1, int *mFaFkTemp2, int mCrossLen1, int mCrossLen2, float *mData ) int vFlag = 0, vCounter1; int vTemp1 ; int vLen ; int FLAG = -1 ; vLen = mCrossLen1 + mCrossLen2 ; / 判断前一部分序列的特性并存储好的序列 vFlag = BestJudger(mMoFkTemp1

33、,mFaFkTemp1,mCrossLen1,mData,vLen ); if(vFlag=2) for( vCounter1 = 0 ; vCounter1<mCrossLen1 ; vCounter1+ ) vTemp1 = *(mMoFkTemp1+vCounter1) ; *(mMoFkTemp1+vCounter1) = *(mFaFkTemp1+vCounter1) ; *(mFaFkTemp1+vCounter1) = vTemp1 ; FLAG = 1 ; / 判断后一部分序列的特性并存储好的序列 vFlag = BestJudger(mMoFkTemp2,mFaFkTe

34、mp2,mCrossLen2,mData,vLen ); if(vFlag=2) for( vCounter1 = 0 ; vCounter1<mCrossLen2 ; vCounter1+ ) vTemp1 = *(mMoFkTemp2+vCounter1) ; *(mMoFkTemp2+vCounter1) = *(mFaFkTemp2+vCounter1) ; *(mFaFkTemp2+vCounter1) = vTemp1 ; FLAG = -1*FLAG ; return(FLAG) ; /* 变异子函数 */void GenAber( int *MotherFlock,int *FatherFlock, int *BestGen, float P, float *mData) int mCounter, mCounter1, mCounter2 ; int mIndexLEN ; int mTemp1 = 0; for( m