实例介绍
【实例简介】
遗传算法解决多维背包问题，说明了遗传算法以及多维背包问题和0-1背包问题的外文文献
212 A Singh and A.s. baghel 2 The Grouping Genetic Algorithm We have developed a steady-state grouping genetic algorithm (SSGGa)for the QMKP. Steady-State genetic algorithm uses steady-state population replacement method [8]. In this method genetic algorithm repeatedly selects two parents, performs crossover and mutation to produce a single child that replaces a less fit member of the population. This is different from generational replacement, where a new population of children is created and the whole parent population is replaced. The steady-state population replacement method has an advantage over generational method due to the fact that the best solutions are always kept in the population and the child is immedi ately available for selection and reproduction. Thus we can possibly find better solu- tions quicker. Moreover with steady-state population replacement method we can easily avoid the multiple copies of the same individual in the population In the gen erational approach multiple copies of the same individual can exist in the population Though these individuals are usually the best individuals, they can rapidly dominate the whole population. In this situation, no further improvement in solution quality is possible without mutation, and often, a much higher mutation rate is required to get further improvements In the steady-state approach the child can be easily checked against the existing population members and if it is identical to any existing individual in the population then it is discarded. In this way the problem of premature conver gence is deterred by disallowing the multiple copies of the same individual in the population. The main features of SsGGa are described below. However, before de- scribing the main features of SSGGA, we need to define the concept of relative value density [5]. The relative value density of an object i with respect to a set S of objects is the sum of its profit value pi and all profit values pii such that e S divided by its weight 2.1 Chromosome Representation Chromosome is represented as set of knapsacks i. e. there is no ordering among the knapsacks. With such a representation there is no redundancy. Every solution is rep resented uniquely 2.2 Fitness Fitness of a chromosome is equal to the overall profit of the solution it represents 2. 3 Crossover Our crossover operator is derived from the crossover operator proposed in [9] for the one-dimensional bin-packing problem. Our crossover operator consists of two phases First phase iteratively builds the child chromosome. During each iteration, it selects one of the two parents uniformly at random and copies the knapsack with largest profit value from the selected parent to the child. Then it deletes all the objects be longing to this knapsack from both the parents and profit values of the knapsacks of A New Grouping Genetic Algorithm for the Quadratic Multiple Knapsack Problem 213 the parents are updated accordingly. This process is repeated K times. The second phase iteratively tries to include as many unassigned objects as it can into the knap sacks without violating the capacity constraints. During each iteration it selects a knapsack at random and adds to it the unassigned object that fits and has highest rela tive value density with respect to the objects already in the selected knapsack. This process is repeated until it becomes impossible to add any more objects to any of the napsac We have used binary tournament selection to select the two parents for crossover, where more fit candidate is selected with probability petter Similar to [5,9] here also crossover and mutation is used in a mutually exclusive manner,i.e. each child is generated by either the crossover operator or the mutation operator but never by both Crossover is applied with probability pc, otherwise muta- tion is used 2. 4 Mutation The mutation operator removes some of the objects from knapsacks. Then it pro ceeds similar to the second phase of crossover operator. We have used 3-ary tour- nament selection to select a chromosome for mutation where the candidate with better fitness is selected with probability 1.0. 3-ary tournament selection is used because more fit chromosome has greater chance of generating a better chromo some after mutation 2.5 Replacement policy The generated child is first tested for uniqueness against the existing population mem bers. If it is unique then it always replaces the least fit member of the population, otherwise it is discarded 2.6 Initial Population Generation Each member of the initial population is generated using a procedure that is derived from greedy heuristic proposed in [5]. The procedure used here differs from the greedy heuristic in that it selects first object of each knapsack randomly from the list of unassigned objects rather than the unassigned object with highest relative density with respect to the list of unassigned objects. Initially all the knapsacks are empty The procedure fills each knapsack one by one. The first object of the knapsack is selected randomly as already described Then objects are added to the knapsack itera tively. During each iteration, an unassigned object that fits and has highest relative value density with respect to the objects already in the knapsack is added to the knap sack. This process is repeated until it becomes impossible to add any more objects to the knapsack. After this the next knapsack is filled in the same way. The whole proc ess is repeated until all the knapsacks have been filled Each newly generated chromosome is checked for uniqueness against the popula- tion members generated so far and if it is unique it is included in the initial population otherwise it is discarded 214 A Singh and A.s. baghel 3 Computational results SSGGA has been coded in C and executed on a Pentium 4 system with 512 MB RAM, running at 2.4 GHz under red-Hat Linux 9.0. In all our experiments with SSGGa we have used Pc=0.6, Better =0.8. Mutation try to remove each object allo cated to a knapsack with probability(2XK/nobj), where nobj is the number of objects allocated to knapsacks with this probability mutation will remove on an average two objects per knapsack. The mutation operator of HJ-Ga [5] also removes two objects from each knapsack. The population size of SSGGa is equal to n, the number of ob- jects in the test instance. All the parameter values were chosen after large number of trials. These parameter values provide good results although these values are in no way optimal for all problem instances. We have tested SsGGa on the same 60 QMKP instances as used by Hiley and Julstrom [5]. These instances are characterized by three things - the density d(proportion of non-zero pi), number of objects n, and the number of knapsacks K. For every instance, the knapsack capacities are set to 80% of the sum of instance's object's weights divided by K. For these instances d is either 0.25 or 0. 75, n is either 100 or 200 and K can take any value from 3, 5, 10) Originally these instances are the instances ot th, resulting in a total of 60 instances availableathttp://cermsem.univ-parisl.fr/soutif/@kp/okp.html.SsggAwasexe cuted 40 times on each instance. each time with a different random seed. during each run both HJ-Ga and HJ-shc generate 20000 candidate solutions. Therefore to allow a fair comparison with HJ-GA and HJ-SHC, SsGGa also generates 20000 candidate solutions Tables I and 2 compare the performance of SsGa with HJ-GA and HJ-SHC. Ta ble l reports the performance of three algorithms on instances with d=0. 25, whereas table 2 reports the same for d=0.75. Data for HJ-Ga and HJ-SHC are taken from [5] For each instance, tables l and 2 report the number of objects n, the number of knap- sacks K in it, its number and knapsacks capacity C. For each of the three approaches on each instance the tables report the best and average value of the solution the stan- dard deviation of solution values and average execution time in seconds Tables 1 and 2 clearly show the superiority of SSGGA over HJ-GA and HJ-SHC Average solution values obtained by ssga are always better than those obtained with Hj-Ga and Hj-shc. In comparison to HJ-Ga, the best solution of ssGGa is better on 56 instances and worse on 4 instances. The best solution of ssga is better than that of hj-rhc on 57 instances and worse on 3 instances HJ-Ga and HJ-shc were executed on Pentium 4, 2.53 GHz system with 1 GB RAM, whereas SSGGa was executed on Pentium 4, 2.4 GHz system with 512 MB RAM. Therefore it is not possible to exactly compare the running times of ssga with those of Hj-ga and HJ-SHC. However on instances with K=3. SSGa is clearly slower to HJ-Ga and HJ-ShC, whereas on instances with K=10, it is clearl faster On instances with K=5, running times of SsGGa are less in comparison to HJ-SHC and roughly the same in comparison to HJ-GA. The running time of HJ-Ga and Hj-shc increases with increase in K. whereas that of ssgga decreases The A New Grouping Genetic Algorithm for the Quadratic Multiple Knapsack Problem 215 区学学剧上 cmocC 品落 图至到到医 >35≌5 Nn mc寸 ∽=5月9 ni cilc寸c寸寸寸寸寸寸寸"vv∽ 落器别图别虽用图导要到图别 落到享训 至至到到到 g荡图导E cm守W|一 8 8 -55|时 G寸-cn寸v| 216 A Singh and A.s. Baghel 到到套到 图到 挥到到 到到烈品洞 目号即烈到到坐居器到 三 导导甚的房网 于 9防月易下别图 守守守|的∞a d n寸的一6m寸一cn寸v c N cn A New Grouping Genetic Algorithm for the Quadratic Multiple Knapsack Problem 217 coSt of mutation operator of ssga, mutation operator of HJ-Ga, which is also the variation operator of Hj-shc, increases with increase in K. This is due to the fact that mutation deletes more objects with increase in K, and as a result more time is spent in subsequent filling of knapsacks with unassigned objects. The cost of crossover opera tor of Hj-ga also increases with increase in K because crossover operator of HJ-ga first copies to the child the object assignments common to both the parents. Clearly common object assignments decreases with increase in K and as a result here also more time is spent in subsequent filling of knapsacks with unassigned objects. This explains the increase in running times of HJ-GA and HJ-SHC with increase in K However, the cost of crossover operator of ssGa decreases with increase in K. This is due to the fact that for small K, the first phase of crossover operator of ssgGa is more disruptive and as a result after the end of first phase, there are lesser number of objects in knapsacks, therefore more time is spent in second phase, which tries to fill the knapsacks to their capacity with unassigned objects. This decrease in crossover cost is more in comparison to increase in mutation cost with increase in K. moreover crossover is used 60%o of times. These two factors together are responsible for the decrease in running time of ssga with increase in K. 4 Conclusions In this paper we have developed a new steady-state grouping genetic algorithm (SSGGA) for the quadratic multiple knapsack problem. We have compared SSGGa with two recently proposed heuristics HJ-Ga and HJ-SHC [5] on 60 QMKP in stances. SSGGA outperformed HJ-Ga and HJ-shC both in terms of best as well as average solution quality. In fact, average solution values obtained by Ssga are always better than those obtained by Hj-Ga and HJ-SHC References 1. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP Completeness. W. HFreeman, San Francisco(1979) 2. Khuri, S, Back, T, Heitkotter, J. The Zero/One Multiple Knapsack Problem and Genetic Algorithms. Proceedings of the 1994 ACM Symposium on Applied Computing, ACM Pre, New York(1994),188-193 3. Cotta, C, Troya, J M. A Hybrid Genetic Algorithm for the 0-1 Multiple Knapsack Prob lem. Artificial Neural Networks and genetic algorithms 3, Springer-Verlag, Berlin(1998) 250-254 4. Yoon, Y, Kim, Y.H., Moon B.R. An Evolutionary Lagrangian Method for the O/1 Multiple Knapsack Problem. Proceedings of the GECCO-2005, ACM Press, New York (2005), 629-635 5. Hiley, A, Julstrom, B.A.: The Quadratic Multiple Knapsack Problem and Three heuristic Approaches to it. Proceedings of the GECCO-2006, ACM Press, New York(2006), 547-552 A. Singh and A.s. baghel 6. Falkenauer, E: New Representations and Operators for GAs Applied to Grouping Prob lems. Evolutionary Computation 2(1992), 123-144 7. Falkenauer, E: Genetic Algorithms and Grouping Problems. John Wiley sons, Chicester (1998) 8. Davis, L. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York(1991) 9. Singh, A, Gupta, A K. Two Heuristics for the One-Dimensional Bin-Packing Problem. To appear in OR-Spectrum(2007) 【实例截图】
【核心代码】
遗传算法解决多维背包问题，说明了遗传算法以及多维背包问题和0-1背包问题的外文文献
212 A Singh and A.s. baghel 2 The Grouping Genetic Algorithm We have developed a steady-state grouping genetic algorithm (SSGGa)for the QMKP. Steady-State genetic algorithm uses steady-state population replacement method [8]. In this method genetic algorithm repeatedly selects two parents, performs crossover and mutation to produce a single child that replaces a less fit member of the population. This is different from generational replacement, where a new population of children is created and the whole parent population is replaced. The steady-state population replacement method has an advantage over generational method due to the fact that the best solutions are always kept in the population and the child is immedi ately available for selection and reproduction. Thus we can possibly find better solu- tions quicker. Moreover with steady-state population replacement method we can easily avoid the multiple copies of the same individual in the population In the gen erational approach multiple copies of the same individual can exist in the population Though these individuals are usually the best individuals, they can rapidly dominate the whole population. In this situation, no further improvement in solution quality is possible without mutation, and often, a much higher mutation rate is required to get further improvements In the steady-state approach the child can be easily checked against the existing population members and if it is identical to any existing individual in the population then it is discarded. In this way the problem of premature conver gence is deterred by disallowing the multiple copies of the same individual in the population. The main features of SsGGa are described below. However, before de- scribing the main features of SSGGA, we need to define the concept of relative value density [5]. The relative value density of an object i with respect to a set S of objects is the sum of its profit value pi and all profit values pii such that e S divided by its weight 2.1 Chromosome Representation Chromosome is represented as set of knapsacks i. e. there is no ordering among the knapsacks. With such a representation there is no redundancy. Every solution is rep resented uniquely 2.2 Fitness Fitness of a chromosome is equal to the overall profit of the solution it represents 2. 3 Crossover Our crossover operator is derived from the crossover operator proposed in [9] for the one-dimensional bin-packing problem. Our crossover operator consists of two phases First phase iteratively builds the child chromosome. During each iteration, it selects one of the two parents uniformly at random and copies the knapsack with largest profit value from the selected parent to the child. Then it deletes all the objects be longing to this knapsack from both the parents and profit values of the knapsacks of A New Grouping Genetic Algorithm for the Quadratic Multiple Knapsack Problem 213 the parents are updated accordingly. This process is repeated K times. The second phase iteratively tries to include as many unassigned objects as it can into the knap sacks without violating the capacity constraints. During each iteration it selects a knapsack at random and adds to it the unassigned object that fits and has highest rela tive value density with respect to the objects already in the selected knapsack. This process is repeated until it becomes impossible to add any more objects to any of the napsac We have used binary tournament selection to select the two parents for crossover, where more fit candidate is selected with probability petter Similar to [5,9] here also crossover and mutation is used in a mutually exclusive manner,i.e. each child is generated by either the crossover operator or the mutation operator but never by both Crossover is applied with probability pc, otherwise muta- tion is used 2. 4 Mutation The mutation operator removes some of the objects from knapsacks. Then it pro ceeds similar to the second phase of crossover operator. We have used 3-ary tour- nament selection to select a chromosome for mutation where the candidate with better fitness is selected with probability 1.0. 3-ary tournament selection is used because more fit chromosome has greater chance of generating a better chromo some after mutation 2.5 Replacement policy The generated child is first tested for uniqueness against the existing population mem bers. If it is unique then it always replaces the least fit member of the population, otherwise it is discarded 2.6 Initial Population Generation Each member of the initial population is generated using a procedure that is derived from greedy heuristic proposed in [5]. The procedure used here differs from the greedy heuristic in that it selects first object of each knapsack randomly from the list of unassigned objects rather than the unassigned object with highest relative density with respect to the list of unassigned objects. Initially all the knapsacks are empty The procedure fills each knapsack one by one. The first object of the knapsack is selected randomly as already described Then objects are added to the knapsack itera tively. During each iteration, an unassigned object that fits and has highest relative value density with respect to the objects already in the knapsack is added to the knap sack. This process is repeated until it becomes impossible to add any more objects to the knapsack. After this the next knapsack is filled in the same way. The whole proc ess is repeated until all the knapsacks have been filled Each newly generated chromosome is checked for uniqueness against the popula- tion members generated so far and if it is unique it is included in the initial population otherwise it is discarded 214 A Singh and A.s. baghel 3 Computational results SSGGA has been coded in C and executed on a Pentium 4 system with 512 MB RAM, running at 2.4 GHz under red-Hat Linux 9.0. In all our experiments with SSGGa we have used Pc=0.6, Better =0.8. Mutation try to remove each object allo cated to a knapsack with probability(2XK/nobj), where nobj is the number of objects allocated to knapsacks with this probability mutation will remove on an average two objects per knapsack. The mutation operator of HJ-Ga [5] also removes two objects from each knapsack. The population size of SSGGa is equal to n, the number of ob- jects in the test instance. All the parameter values were chosen after large number of trials. These parameter values provide good results although these values are in no way optimal for all problem instances. We have tested SsGGa on the same 60 QMKP instances as used by Hiley and Julstrom [5]. These instances are characterized by three things - the density d(proportion of non-zero pi), number of objects n, and the number of knapsacks K. For every instance, the knapsack capacities are set to 80% of the sum of instance's object's weights divided by K. For these instances d is either 0.25 or 0. 75, n is either 100 or 200 and K can take any value from 3, 5, 10) Originally these instances are the instances ot th, resulting in a total of 60 instances availableathttp://cermsem.univ-parisl.fr/soutif/@kp/okp.html.SsggAwasexe cuted 40 times on each instance. each time with a different random seed. during each run both HJ-Ga and HJ-shc generate 20000 candidate solutions. Therefore to allow a fair comparison with HJ-GA and HJ-SHC, SsGGa also generates 20000 candidate solutions Tables I and 2 compare the performance of SsGa with HJ-GA and HJ-SHC. Ta ble l reports the performance of three algorithms on instances with d=0. 25, whereas table 2 reports the same for d=0.75. Data for HJ-Ga and HJ-SHC are taken from [5] For each instance, tables l and 2 report the number of objects n, the number of knap- sacks K in it, its number and knapsacks capacity C. For each of the three approaches on each instance the tables report the best and average value of the solution the stan- dard deviation of solution values and average execution time in seconds Tables 1 and 2 clearly show the superiority of SSGGA over HJ-GA and HJ-SHC Average solution values obtained by ssga are always better than those obtained with Hj-Ga and Hj-shc. In comparison to HJ-Ga, the best solution of ssGGa is better on 56 instances and worse on 4 instances. The best solution of ssga is better than that of hj-rhc on 57 instances and worse on 3 instances HJ-Ga and HJ-shc were executed on Pentium 4, 2.53 GHz system with 1 GB RAM, whereas SSGGa was executed on Pentium 4, 2.4 GHz system with 512 MB RAM. Therefore it is not possible to exactly compare the running times of ssga with those of Hj-ga and HJ-SHC. However on instances with K=3. SSGa is clearly slower to HJ-Ga and HJ-ShC, whereas on instances with K=10, it is clearl faster On instances with K=5, running times of SsGGa are less in comparison to HJ-SHC and roughly the same in comparison to HJ-GA. The running time of HJ-Ga and Hj-shc increases with increase in K. whereas that of ssgga decreases The A New Grouping Genetic Algorithm for the Quadratic Multiple Knapsack Problem 215 区学学剧上 cmocC 品落 图至到到医 >35≌5 Nn mc寸 ∽=5月9 ni cilc寸c寸寸寸寸寸寸寸"vv∽ 落器别图别虽用图导要到图别 落到享训 至至到到到 g荡图导E cm守W|一 8 8 -55|时 G寸-cn寸v| 216 A Singh and A.s. Baghel 到到套到 图到 挥到到 到到烈品洞 目号即烈到到坐居器到 三 导导甚的房网 于 9防月易下别图 守守守|的∞a d n寸的一6m寸一cn寸v c N cn A New Grouping Genetic Algorithm for the Quadratic Multiple Knapsack Problem 217 coSt of mutation operator of ssga, mutation operator of HJ-Ga, which is also the variation operator of Hj-shc, increases with increase in K. This is due to the fact that mutation deletes more objects with increase in K, and as a result more time is spent in subsequent filling of knapsacks with unassigned objects. The cost of crossover opera tor of Hj-ga also increases with increase in K because crossover operator of HJ-ga first copies to the child the object assignments common to both the parents. Clearly common object assignments decreases with increase in K and as a result here also more time is spent in subsequent filling of knapsacks with unassigned objects. This explains the increase in running times of HJ-GA and HJ-SHC with increase in K However, the cost of crossover operator of ssGa decreases with increase in K. This is due to the fact that for small K, the first phase of crossover operator of ssgGa is more disruptive and as a result after the end of first phase, there are lesser number of objects in knapsacks, therefore more time is spent in second phase, which tries to fill the knapsacks to their capacity with unassigned objects. This decrease in crossover cost is more in comparison to increase in mutation cost with increase in K. moreover crossover is used 60%o of times. These two factors together are responsible for the decrease in running time of ssga with increase in K. 4 Conclusions In this paper we have developed a new steady-state grouping genetic algorithm (SSGGA) for the quadratic multiple knapsack problem. We have compared SSGGa with two recently proposed heuristics HJ-Ga and HJ-SHC [5] on 60 QMKP in stances. SSGGA outperformed HJ-Ga and HJ-shC both in terms of best as well as average solution quality. In fact, average solution values obtained by Ssga are always better than those obtained by Hj-Ga and HJ-SHC References 1. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP Completeness. W. HFreeman, San Francisco(1979) 2. Khuri, S, Back, T, Heitkotter, J. The Zero/One Multiple Knapsack Problem and Genetic Algorithms. Proceedings of the 1994 ACM Symposium on Applied Computing, ACM Pre, New York(1994),188-193 3. Cotta, C, Troya, J M. A Hybrid Genetic Algorithm for the 0-1 Multiple Knapsack Prob lem. Artificial Neural Networks and genetic algorithms 3, Springer-Verlag, Berlin(1998) 250-254 4. Yoon, Y, Kim, Y.H., Moon B.R. An Evolutionary Lagrangian Method for the O/1 Multiple Knapsack Problem. Proceedings of the GECCO-2005, ACM Press, New York (2005), 629-635 5. Hiley, A, Julstrom, B.A.: The Quadratic Multiple Knapsack Problem and Three heuristic Approaches to it. Proceedings of the GECCO-2006, ACM Press, New York(2006), 547-552 A. Singh and A.s. baghel 6. Falkenauer, E: New Representations and Operators for GAs Applied to Grouping Prob lems. Evolutionary Computation 2(1992), 123-144 7. Falkenauer, E: Genetic Algorithms and Grouping Problems. John Wiley sons, Chicester (1998) 8. Davis, L. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York(1991) 9. Singh, A, Gupta, A K. Two Heuristics for the One-Dimensional Bin-Packing Problem. To appear in OR-Spectrum(2007) 【实例截图】
【核心代码】
标签：
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论