多背包问题求解及其在网络化制造中的应用.pdf

《多背包问题求解及其在网络化制造中的应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、机械设计与制造第5期72MachineryDesign&Manufacture2010年5月文章编号：1001—3997(2010)05—0072～03多背包问题求解及其在网络化制造中的应用董朝阳蔡安江阮晓光(西安建筑科技大学，西安710055)Solutionofmultiple—knapsackproblemandItsapplicationinnetworkedmanufacturingDONGZhao—yang，CAIAn-jiang，RUANXiao-guang(xi’anUniversityofArchitectureandTech

2、nology，Xi’an710051，China)【摘要】给出了多背包问题及其数学描述；讨论了网络化制造中的最优制造伙伴选择问题，将其归j；结为一种复杂的多目标、多选择、多约束背包问题并提出了一种并行多目标妥协遗传算法进行求解；算法i采用基于排列的编码方式，由多个种群独立进化并定期交换最佳个体，而适应度计算采用自适应权重方《法及基于距离度量的妥协方法，通过基于小生境技术的适应度共享保持种族多样性，最终求得决策者可{接受的妥协解。j；关键词：多背包问题；网络化制造；优化配置；并行多目标妥协遗传算法i【Abstract】Themultiple-kn

3、apsackproblemanditsmathematicaldescriptionareanalyzedThes8一{lectionofoptimummanufacturingpartnersinnetworkedmanufacturingisdiscussed．Theproblemisranged{to。complicatedmultiple_objective，multiple—choice，andmultiple—constraintknapsackproblem，andni；compromise,basedparallelmultip

4、le—objectivegeneticalgorithmisproposedtosolveit．Thealgorithmusesithecodingmethodbasedonpermutation，andithas血numberofsubpopulationswhichevolveindepen-《dentlyandexchangethebestchromosomeswitheachother．Theadaptiveweightsapproachandthecom-{promisedapproachbasedondistanceareusedf

5、ordeterminingthefitnessofchromosomes，andfitnessi；sharingmethodisalsousedforkeepingthepopulationdiversity．Finally，thecompromisedsolutionisob-itainedforthedecision-maker．{Keywords：Multiple-knapsackproblem；Networkedmanufacturing；Optimizingconfiguration；{Compromise-basedparallel

6、multipleobjectivegeneticalgorithm3中图分类号：TH166文献标识码：A型如式(1)所示：1引言多目标、多选择、多约束背包问题可以被描述成为：设有n类∑∑c相互排斥的物品，每一类物品共有个物件；物件有多种属性，例如，价值、美观性、实用性、重量、体积、可靠性等，可设物件骱1∑Eb(其中，i为物品类的下标，1，⋯，n；j为每个物品类中物件的下1∑∑P标=l，⋯，ni)的价值为c，美观性为6，实用性为P，重量为W，体积为也，可靠性为等；上述物件要装入一个有多种约束条件1Subjectto=1，i=1，⋯，n的背包，例如

7、，重量约束、体积约束、可靠性约束等，可设背包的最J=1nn大容纳重量为，最大容纳体积为D，最低可靠性为R等；可定∑∑义‰为决策变量，如果物件毋被选人背包时，=1，否则=0；背∑∑西<-D包内物件的总价值为∑∑c，总美观性为∑∑6，总实i=l，：lni=1J=1i=1J=1nnnnn-n∑≥R用性为∑∑p，总重量为∑∑，总体积为∑∑i=1J=1，6i=1』=li=1=1i=1』1Vi,j，E{0，1}，i∈{1，⋯，n}√∈{1，⋯，n总可靠性为13∑等。多目标、多选择、多约束背包问题就是Iti式中：6、、d、、W、D、及R一正值；约束条件∑：1

8、，i=1，从每个物品类中选择一个物件使得在满足背包重量、体积、可靠．J=1⋯，r一每个物品类中必须选择并只能选择一个物件。性等多种约束条件下最大化价值