整箱货物的混合装箱问题的遗传解法

维普资讯 http://www.cqvip.com

中国科ｌ技１言息２００７年第２２期　ＣＨＩＮＡ　ＳＣＩＥＮＣＥ　ＡＮＤ　ＴＥＣＨＮＯＬＯＧＹ　ＩＮＦＯＲＭＡＴＩＯＮ　Ｎｏｖ．２００７　执行基本遗传算法时，有４个参数需　要事先指定。它们是群体的人小Ｍ、交　叉概率Ｐ　变异慨率Ｐ　及终止的代数Ｔ。　（１）群体大小Ｍ：群体的大小Ｍ表示　群体中所含个体的数量。当Ｍ取值较小　时，叮提高遗传算法的运算速度，但却降　低了群体的多样性，有可能会引起遗传算　法的早熟现象；而当Ｍ取值较夫时，又　会使得遗传算法的运行效率降低。一般建　通过个体适应值的大小来评价群体中　个体所对应装载方案的优劣。对于违反装　载质鼍约束、装载容积约束的个体，在求　解其适应值的过程中要给予相应的惩罚以　４到第２Ｏ位随机选取。本例随机选取第７　到第ｌ０位交叉和第ｌ　５到第２０位交叉。　２．３整箱货物　己送的混合装箱算法步骤　各项参数和遗传算子确定后，求解集　装箱整箱货物配送的混合装箱问题的遗传　算法步骤如下，算法流程图如图２所示。　Ｓｔｅｐ　ｌ：确定问题采取的编码方式及　算法群体规模Ｍ、最大迭代代数Ｔ、交叉　概率Ｐ　硬变异概率Ｐ…的值。令迭代代数　确保符合条件的较优个体有较大的生存机　会。对于违反约束条件的个体的适应度值　可由下式计算：　ｆ　ｉ　ｔ　ｎ　ｅ　ｓ　ｓ（Ｃ，　’）　ｆ（Ｘ）　Ｃ　议的取值范围是２０～ｌ００。　（２）交叉概率Ｐ　’．交叉操作是遗传算法　中产生新个体的主要方法，所以交叉概率　一般应取较大值。但若取值过大．它又会　破坏群体中的优良模式，对进化运算反而　产生不利影响；若取值过小，产生新个体　的速度又较慢，　般建议的取值范围是０．　４～１．００。　（３）变异概率Ｐ．．．：若变肆溉率Ｐ．．取值　较大，虽然能够产生出较多的新　体，　也有可能破坏很多较好的模式，使得遗传　算法的性能近似于随机搜索算法的性能；　若变异概率Ｐ…取值太小，　１变异操作产生　新个体的能力千【１抑制早熟现象的能力就会　较差。一般建议的取值范　是０．Ｏ０ｌ～０．　１。　（４）终止代数Ｔ：终止代数Ｔ是表示遗　传算法运行结束条件的一个参数，它表示　遗传算法运行到指定的进行代数之后就停　止运行。一一股建议的取值范围是ｌ　０　０～　１　０００。　这４个参数对遗传算法的搜索效果砭　搜索效率都有　定影响　日前尚无合理选　择它们的理论根据。仕遗传算法的实际应　用中，往往需要经过多次的．畎算岳才能确　定出这些参数合理的取值范围或取值夫小　２．２算法的具体吱观　（１）．编码预处理　首先要对优化　题的解进　的编　码，本文采用０，ｌ＿二进制常规　。以第　种货物的配装状态Ｘ怍为染色体ｆｆＪ的第ｉ　遗传基因，每条染色体上彳『ｎ个遗传　因，即染色体的编码形　为（Ｘ　，　Ｘ　，…，Ｘ，…，Ｘ），每・摹凼的取　值为０，ｌ。即当ｘ一０时，表示第ｉ种　货物不配装；当ｘ　ｌ时，表示第ｉ补货　物配装。每一种编码方式表示货物　集装　箱中的一种混载方法。　Ｊ如，对十　批货　物种类数为２　０．若其装箱编码方』弋为　０ｌ０００１　ｌ０００１　ｌ０００１００００，解码聒的对丘　载方案为：第２、６、７、ｌ　ｌ、ｌ　２，ｌ　６　种货物配装，其余不配装。　（２）．确定适应值凼数　∑ｍ￣Ｌｘ［Ｏ　ｆ　）］：　（１．３）　ｋ　０：　其中，ｈ　（ｘ）＝　Ｖ　（１．４）　Ｓｔｅｐ２：随饥产生Ｍ个不同个体　（ｓ　ｌ，２，３，…，Ｍ），构成初始群体Ｍ“　ｈ　（ｘ）一　ｇ　Ｇ　（１．５）　（，　，∥　，…，∥’）；　式中：（１．４）为货物装载总容积惩罚函　Ｓｔｅｐ３：若ｋ＝Ｔ，停止计算，将所　数；（１．５）式为货物装载总质量惩罚函数；　得的，…值按照大小降序排列，令ｔ　为最　ｒ为模型中约束方程的个数；Ｃ为惩罚因　大值。输出最大值ｔ　。ｔ。为集装箱的优化　子，在计算时可取为一充分大的正数；ｋ　装载结果，解码后即为货物在各集装箱中　为遗传代数；　’为第ｋ代第ｉ个个体。将　的优化装载方案。否则转ｓｔｅｐ４；　（１．４）式和（１．５）式代入（１．３）式，可得　Ｓｔｅｐ４：计算个体适应度值ｆｉｔｎｅｓｓ　ｆ　ｉ　ｔ　１３　ｅ　ｓ　ｓ（Ｃ，　’）＝ｆ（ｘ）　Ｃ　（　’），并将个体　按照适应度值大小降序　｛ｉｎａｘ［０，　一｝　｝＋ｍａｘ［０，∑ｇ　ｒＧ　（１．６）　排列，排序后个体，…为本代群体中的最优　所以，第ｋ代个体ｉ的适应值函数为：　个体，个体ｔ　ｉ：’为本代群体中的最劣个体；，　Ｓｔｅｐ５：进行复市ＩＪ操作，即将本代群体　ｆ　葶暮　－杀　－．＿ｌ　中最劣个体ｆ　替换为上一代中最优个体　ｉｆ｛Ｉｌｌｓ　ｃ　，　￡ｒ　ｍ￣ｘ［ｏ∑¨　ｊ　，并对群体中相同个体进行“一个保　—ｍａｘ［０∑ｇ　一Ｇｊ　Ｉ　蔫匠　事每。　１．ｉ　留，其余删除”的操作，删除个体分别用　（３）．遗传操作方法　ｓｔｅｐ２随机产生的个体替换；　存交叉过程中，由于某些双亲采用常　Ｓｔｅｐ６：按照概率Ｐ　Ｐ　对个体仿效　规的＿｛叉亲捉了法可能造成父代与子代完全　执行交叉操作、变异操作，令ｋ－－ｋ＋ｌ，　相同．这样势必影响收敛速度和搜索范围。　返回ｓｔｅｐ３。　同时．由下本文示例中染色体长度较长，采　３应用举例　用单交配位法势必影响收敛速度。所以，本　现有一５　Ｄ集装箱，内容积为９．　文采刑变化交配与　交配位相结合的交配　１　ｌｍ　，载重量为５０００ｋｇ，有一批待装货　方；＇去，具体交配过程如图ｌ所示。　物的相关数据　表ｌ。将待装货物按照适当　若按常规方法，选交配位在ｌ，２，３，则　的混装方法装人该集装箱＿ｆｌ】，使得该箱的　这样的交配　任何变化，因此，应该避开　内容积得到充分利用。根据以　所述的基　达三个位置。采用变化交配法：从　开始　本遗传算法的运行参数，确定各初始参数　先比较两父代的相同的荩因，从不同基因　位置按常觇方法随饥选交配位。如比较　ｌｌ输Ａ　　Ｍ、Ｔ、　、　Ｉ｛　一～一　——　面　例　ｓｓｓｄｓｄｓｓｄｄｄｄｄｓｓｓｓｓｄｓ，其中Ｓ　ｌ随机产生视始群ｌ体＾，　：０　表示卡｝Ｊ同．ｄ表示４　同。交配位＿ｎ『以在第　■　琵童　、０　．，一，　一　—　：　＾ｔ：＾０曩　０　Ｏ０ｉ　ｌｏ００：：１００　０ｌｏ０Ｏ０　▲　计算　捧适应度馇ｉ　｝至叉　ｔ　ｌ　Ｅａｒｅ　ｔ：　０　１；０；　００　ｌ０ｌｌ：００ｉ０　０ｌｏ０ｌ０　ｋ—ｌ　ｌ复翩，将　一一‘　Ｉ　ＩＩ　—ｌ—依据概军Ｐ执行耍里撩作　———————　———～　００　１　１０１１　ｉ　００　０ｌｏ。ｌ０　ｌ　———　ｉＯ０　ｌ０Ｏ０；∞：０　０ｌｏ０ｏ０　依据概章只执行变异操作　交叉过程　图２　整箱配送的混合装箱遗传算法流程图　３２８　维普资讯 http://www.cqvip.com

的选取如下：算法群体规模Ｍ　１Ｏ０，交叉舰率Ｐ　０．９０．变　异溉率Ｐ…０．０２，最大迭代代数Ｔ＝～１ＯＯ，惩罚　予ｃ　１Ｏ０。　本文就此算例用ＶＢ编　了遗传算法的程序，连续做了１０次　实验，每次实验耗时为１　Ｓ，所得结果如表２所示。　由表２呵知，最佳装箱方案为：６，７，１２，１３，１４，１５，１６，２０号货物　装入箱中，此时的装载货物重量为４４０４ｋ￣，体积为９．１　１ｍ　，籍容　利用率为１　００％。　［６］ｌ、雷，尹传忠，蒲云．集装箱运输多箱三维装载优化问　题的遗传算法［Ｊ］．铁道学报．２００４－，４．　［７］顾洁，范春菊．ＴＳＰ的混合遗传算法一人工神经网络模型　¨ＪＩ．电力系统及其自动化学报．２００Ｉ，Ｉ．　悔巷｜奄　灸　ｌｌ　＿　＿　ｌｌ　学位｜　，　｜　ｌ　黄娟性别：女出生年月：１　９　７４年４月向　物流管理　硕士主要研究方　结论　１．遗传算法　搜索过程中不容易陷丁局部最优，　便所定义　的适应度函数是不连续的、非规则的情况下，它也能以很大的慨　率找列整体最优解，囚而具有较好的全局最优解的求解能力。　２．由于遗，专算法　旮的并行性，非常适用Ｔ大规使』ｆ　行计　算。　３．遗，专算法花求解较复杂问题时，能较快速、较理想地计算　出最终解。　上接第３２６页　预定海域时，激光束以一定形－Ｊ￣（ａｎ　１　５千米长１千米宽的矩形）扫过目　标海域，完成对水ｌ－ｉＩ艇的广播式通信。该系统对战术潜艇艰　效。如果飞机高度为１万米，以３００米／秒速度飞过潜艇上空，激光　束将　海面上扫过一条１５千米宽的照射带。住飞机一次飞过潜艇　｝＝空约３秒的时间内，可完成４０～８０个汉字符号信息量的通讯。ｊｘＬ＿　种方法实现起来较为容易，在条件成熟时，很容易将这种办法升级列　天基系统中。　表１　待装货物的相关数据　辱装赞　：　、　ｌｈ　ｊ：０　０：０　：３：　０　ＳＯ　０　：０９　５结束语　通信的』发展日新月异，通信频谱从极长波延伸至毫米波、　畦毫　米波乃至激光与粒子通信范畴。对干潜艇通信，寻求具有适十深　水、高数据率、保密性好，抗干扰强特点的通信技术，将是新｛ｊ＝｝＝纪　的发展方向。蓝绿激光对潜通信可以使潜艇在深海海域进行收信，　保证了潜艇的隐蔽性和机动　，而且通信的抗干扰能力强、通信容　量大、数据率高，因而具有很好的应用前景。所以美国海军曾预　言：到２０世纪末蓝绿激光将取代现有ＥＩ　Ｆ通信系统。　然而，蓝绿激光对潜通信系统也有缺点：气象条什和海况条什对　通信仍然行～・定的影响。因此前苏联曾认为解决对潜通信的最好　占　￡ｅ９　￡茁　ｊ　７，９５　：ｊ　｛７　悲　鸶蓑簧錾ｌ　Ｖ　ｉ：　ｊ　：　０　７　０　ｅ　０　Ｓ｛　？ｊ９　２０　：￡３　掌　＾；　ｊ０；　ｅ：｛　§　；一；　｛一：　９９　湃　表２计算结果　宴验　豢　装篷蝮餐　ｎ　ｒ’Ｏ００００００　００　｛ｎ　０　＾０　Ｏ０　Ｏ！Ｏ０’１Ｏｎｌ｛－ｉ　＾　１　７　０　蒜错　辜　ｊＳ　ｊｉ　？　‘　萋饕ｊ豫　９　０ｊ　Ｓ　７　＾ｎ＾豫　＾＾　ｎ☆ｎ—　ｅ　．９　Ｓ　ｉ９　｛ｉ０　１　．　｛　Ｉｊ　』　’　：２，３　，　０　３　６　０　！　Ｓ．　３　０　０ｊ　Ｏ０１０００００　ｊＯ０ｉｊ０００００　；ｎ０ｊ０ｊ　００００ｉ０ｉ０１Ｏｎ’＾　ｌ　ｌ００　０００００）３００００００　办法是实施全面通信手段，保证系统最大限度的可靠性。即将蓝绿　激光对潜通信系统和甚低频、超低频通信系统结合起来，相互补充，　保障潜艇在不同条件下的通信联络。　因此，对潜通信的发展趋势很可能是蓝绿激光通信系统为主，　ＥＬＦ、ＶＩ　Ｆ系统为辅，两种系统相辅相成，互为补充，从而更好地完　善对潜通信系统，提高潜艇的战斗力和生存能力。　ｎ’　＾　＾ｌＩ　ｒ＾　ｎ　：　｛ｅ　争　：ｉ　５，ｊｊ　ｉＳ　：０　８　Ｓ　ｅ　８　９：　９　ｉ　ｉ０００００：００００００００ｉ１　０　００００ｌＯ０００ＯＯｊｉ：０ｉ１０００　拇　｛００００１：Ｏ０Ｏ０ｉ：ｉｉｉ０００：　ｊ　ｊ　６　．ｉ：！：　｛　６、ｊ　６　ｉ：！ｉ｝，ｉ；ｉ５．：　２０　鸯蜃　＝　连　＿　０　０２５６４　话准量　爨　童　）００００ｊ　ｉ＠９００ｉ　ｉ　ｌｉ０００：　？　２　５　；：５．　§２０　９　ｊｉ　参考史　参壹　最慧。　｜－　薯　。　ｌ　｜罄　誊＿　ｌ　ｌ＿　镶　＿ｌｉ＿　＿　。　…杨正兴，梁玉军，张静，田培根．蓝绿激光对潜通信研究［Ｊ］．光机电　信息，２００６，２：４８—５　７．　［２］夏维华，王一璐．潜艇通信系统综述．计算机与网络［Ｊ＿．２００２，５５－　５７．　［１＿姜宏主编．物流运输技术与实务［Ｍ］．北京：人民交通出版　社．２ＯＯ１．１　０．　［５］赵长明，黄杰．未来激光探潜和对潜通信技术的发展［Ｊ］．光学　［２］邢文训，谢金星．现代优化计算方法［Ｍ］．清华大学出版祉．　２００５．１　２．　［５］卜雷，刘海旭，蒲云，尹传忠．遗传算法确定零担贷　物的选择装箱方式［Ｊ＿．交通运输工程学报．２００２，９．　［４］韩健，林友联．最优化方法［Ｍ］．天津大学出版社．２　００４，　ａ　技术．２００１，２７（１）：５５－５６．　［４］曲晓慧，王红星．国内外对潜通信的发展及现状［Ｊ＿，舰船论证参　考．２００４（２）：１９－２４．　［５＿谭显裕．激光对潜通信的作用及前景［Ｊ＿．光电子技术．１　９９５，１　５（５）：　２９－５５．　［５］云庆夏，黄光球，王战权．遗传算法和遗传规划［Ｍ］．冶　金工业出版社．１　９９　７，４．　毒消食　｜　＿　ｔ叠　ｉ　＿＿　＿　｜　奚小明，男　１　ｇ　８　７年生，国防科学技术大学光电科学与工程学院　军用光电专业　３２９