| Input Data Dependency of a Genetic Algorithm to Solve the Set Covering Problem |
| |
| 作者姓名： | KakuzoIwamura MakotoHoriike TomoyaSibahara |
| |
| 作者单位： | [1]DepartmentofMathematics,JosaiUniversity,Japan,kiwamura [2]FacultyofEconomics,TeikyoUniversity,Japan,mhoriike [3]NagoyaGameDesignerSchool,Japan |
| |
| 摘 要： | A genetic algorithm to solve the set covering problem proposed in the literature had some improvements which gave better solutions, i.e., better chromosomes in the first starting population, taking full account of domain specific knowledge with sound programming skill. We have further investigated the input data dependency of their genetic algorithm, i.e., the dependency on costs and density. We have found that for input problem data sets with densities greater than or equal to 3%, our genetic algorithm is still practical both in computing time and approximation ratio.
|
| 关 键 词： | 遗传算法 集合覆盖问题 数据输入 规划问题 |
Input Data Dependency of a Genetic Algorithm to Solve the Set Covering Problem |
| |
| KakuzoIwamura MakotoHoriike TomoyaSibahara.Input Data Dependency of a Genetic Algorithm to Solve the Set Covering Problem[J].Tsinghua Science and Technology,2003,8(1):14-18. |
| |
| Authors: | Kakuzo Iwamura Makoto Horiike Tomoya Sibahara |
| |
| Abstract: | A genetic algorithm to solve the set covering problem proposed in the literature had some improvements which gave better solutions, i.e., better chromosomes in the first starting population, taking full account of domain specific knowledge with sound programming skill. We have further investigated the input data dependency of their genetic algorithm, i.e., the dependency on costs and density. We have found that for input problem data sets with densities greater than or equal to 3%, our genetic algorithm is still practical both in computing time and approximation ratio. |
| |
| Keywords: | input data dependency set covering problem genetic algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
