遗传算法解决车辆路径问题.doc

下面的源代码是解决车辆路径问题的。谈一点经验性的东西，就是在进行染色体交叉时，一定要注意基因结构的问题。根据具体应用情况，尽量要保证好的基因结构遗传到后代中。其实此时的交叉变异等所有的操作，考虑的是基因结构，而不是单个的基因。所以在设计编码方式时就要考虑到设计出良好的基因结构。便于分割和组合的结构是好的设计。 /* 最优化函数 */void GAOptim( float *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( mCounter1 = 0 ; mCounter1FLOCKSIZE ; mCounter1+ ) pTemp1 = MotherFlockmCounter1 ; PermutRnd( LEN , 1 , pTemp1 ) ; for( mCounter1 = 0 ; mCounter1FLOCKSIZE ; mCounter1+ ) pTemp1 = FatherFlockmCounter1 ; PermutRnd( LEN , 1 , pTemp1 ) ; PermutRnd( LEN , 1 , mBestGen ) ; / 初始化最优种群 for( mCounter = 0 ; 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 ) = 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, mFaFkTemp2LEN ; int mMotherFlockFLOCKSIZELEN , mFatherFlockFLOCKSIZELEN ; int mChildFlock2*FLOCKSIZELEN ; int mIndex1LEN, mIndex2LEN ; int *pMo, *pFa, *pChid ; pMo = mMotherFlock0 ; pFa = mFatherFlock0; pChid = mChildFlock0 ; for(mCounter = 0 ; mCounterFLOCKSIZE*LEN ; mCounter+) *( pMo + mCounter ) = *( MotherFlock + mCounter ) ; *( pFa + mCounter ) = *( FatherFlock + mCounter ) ; for( mCounter = 0 ; mCounterFLOCKSIZE ; mCounter+ ) /* 进行双亲双子交叉 */ / 产生交叉点 mIndex = floor( UniRnd()*LEN ) ; / 根据交叉点，寻找两段合适的遗传序列 for( mCounter1 = 0 ; mCounter1LEN ; mCounter1+ ) / 数组初始化 mMoFkTemp1mCounter1 = 0 ; mMoFkTemp2mCounter1 = 0 ; mFaFkTemp1mCounter1 = 0 ; mFaFkTemp2mCounter1 = 0 ; / 存储四段序列 for( mCounter1 = 0,mCounter2 = 0,mCounter3 = 0 ; mCounter1LEN ; mCounter1+ ) if(mCounter1mIndex) mMoFkTemp1mCounter2 = mMotherFlockmCountermCounter1 ; mFaFkTemp1mCounter2 = mFatherFlockmCountermCounter1 ; mCounter2+ ; else mMoFkTemp2mCounter3 = mMotherFlockmCountermCounter1 ; mFaFkTemp2mCounter3 = mFatherFlockmCountermCounter1 ; mCounter3+ ; mCrossLen1 = mIndex - 1 ; mCrossLen2 = LEN - mCrossLen1 ; / 将两段好的序列放在mMoFkTemp1,mMoFkTemp2中，差的放在mFaFkTemp1,mFaFkTemp2中 mCrossFlag = BestChip(mMoFkTemp1,mMoFkTemp2,mFaFkTemp1,mFaFkTemp2,mCrossLen1,mCrossLen2,vData) ; / 根据两段序列构造完整基因，存放在子代中 PermutRnd( mCrossLen1 , 1 , mIndex1 ) ; / 产生补充基因的随机数 PermutRnd( mCrossLen2 , 1 , mIndex2 ) ; for( mCounter1 = 0, mCounter2 = 0 ; mCounter1LEN ; mCounter1+ ) if(mCounter1=mCrossLen1) mChildFlock2*mCountermCounter1 = mMoFkTemp1mCounter1 ; if(mCrossFlag=1) /如果交叉成功,则补充基因,否则直接复制到子代 mChildFlock2*mCounter+1mCounter1 = mFaFkTemp1 mIndex1mCounter1 ; else mChildFlock2*mCounter+1mCounter1 = mFaFkTemp1mCounter1 ; else mChildFlock2*mCountermCounter1 = mMoFkTemp2mCounter2 ; if(mCrossFlag=1) mChildFlock2*mCounter+1mCounter1 = mFaFkTemp2 mIndex2mCounter2 ; else mChildFlock2*mCounter+1mCounter1 = mFaFkTemp2mCounter2 ; mCounter2+ ; / 最后把产生的子代转入到输入参数ChildFlock中 for ( mCounter = 0 ; mCounter2*FLOCKSIZE*LEN ; mCounter+ ) *( ChildFlock+mCounter ) = *( pChid+mCounter ) ; / 子函数，将输入的四段基因中最好的两段存放在mMoFkTemp1和mMoFkTemp2中/ 返回交叉信息，返回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,mFaFkTemp1,mCrossLen1,mData,vLen ); if(vFlag=2) for( vCounter1 = 0 ; vCounter1mCrossLen1 ; vCounter1+ ) vTemp1 = *(mMoFkTemp1+vCounter1) ; *(mMoFkTemp1+vCounter1) = *(mFaFkTemp1+vCounter1) ; *(mFaFkTemp1+vCounter1) = vTemp1 ; FLAG = 1 ; / 判断后一部分序列的特性并存储好的序列 vFlag = BestJudger(mMoFkTemp2,mFaFkTemp2,mCrossLen2,mData,vLen ); if(vFlag=2) for( vCounter1 = 0 ; vCounter1mCrossLen2 ; 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( mCounter = 0 ; mCounterUniRnd() ) /当满足变异概率时进行变异母代 PermutRnd( LEN , 1 , mIndex ) ; mTemp1 = *(MotherFlock+mCounter*LEN+mIndex1) ; *(MotherFlock+mCounter*LEN+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( PUniRnd() ) /当满足变异概率时进行变异父代 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) = *(FatherFlock+mCounter*LEN+mIndex4) ; *(FatherFlock+mCounter*LEN+mIndex4) = m