文献

J-GLOBAL ID：201702254994974654   整理番号：17A0257427

遺伝的アルゴリズムに基づく割引{0-1}ナップサック問題の解明に関する研究【JST・京大機械翻訳】

Research on Genetic Algorithms for the Discounted{0-1}Knapsack Problem

著者 (5件)： He Yichao (College of Information Engineering,Shijiazhuang University of Economics) ,  Wang Xizhao (College of Computer Science and Software Engineering,Shenzhen University) ,  Li Wenbin (Laboratory of Network and Information Security,Shijiazhuang University of Economics) ,  Zhang Xinlu (College of Mathematics and Information Science,Hebei Normal University) ,  Chen Yiying (College of Information Engineering,Shijiazhuang University of Economics)
資料名： Jisuanji Xuebao  (Jisuanji Xuebao)
巻： 39  号： 12  ページ： 2614-2630  発行年： 2016年 
JST資料番号： C2531A  ISSN： 0254-4164  CODEN： JIXUDT  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 中国 (CHN)  言語： 中国語 (ZH)

抄録/ポイント： 現在,割引{0-1}ナップサック問題(D{0-1}KP)を解決するための主要なアルゴリズムは,動的計画法に基づく多項式時間決定論的アルゴリズムであり,D{0-1}KP事例における価値係数と重み係数が大きい範囲にある場合には実用性がない。本論文では,D{0-1}KPを解くために,杰出者保存戦略遺伝的アルゴリズム(EGA)に基づいて,D{0-1}KPの2つの新しい数学モデルを確立した。次に,EGAと第一の数学モデルを用いて,D{0-1}KPを解決するために,非正規符号化個体のための欲張り修復と最適化アルゴリズムアルゴリズムを提案し,EGAと結合して,D{0-1}KPを解くための最初の遺伝的アルゴリズムアルゴリズムを提案した。第二に,EGAと第二の数学モデルを用いて,D{0-1}KPを解決し,非正規符号化個体を処理するもう一つの有効なアルゴリズムNROAを提案し,EGAと結合してD{0-1}KPを解く第二の遺伝的アルゴリズムSECEGAを提案した。最後に,4つの大規模なD{0-1}KPの事例を用いて,FIREGAととの交差確率と突然変異確率の合理的値を決定し,2つのアルゴリズムの実際の性能を比較した。4種類の事例の計算結果を示した。FIREGAとSECEGAは大規模なD{0-1}KPの事例を解くのに非常に適しており、1つの近似比が1に近い近似解が得られ、しかもFIREGAの平均求解性能はSECEGAより優れている。Data from the ScienceChina, LCAS. Translated by JST【JST・京大機械翻訳】

シソーラス用語： 近似法 ,  符号化 ,  *アルゴリズム ,  動的計画法 ,  *遺伝的アルゴリズム ,  突然変異 ,  数学モデル ,  *ナップサック問題
準シソーラス用語： 近似解 ,  最適アルゴリズム ,  実用性 ,  重み係数 ,  決定論 ,  多項式時間 , 【Automatic Indexing@JST】

著者キーワード (5件)： discounted{0-1}knapsack problem ,  genetic algorithm ,  non-normal coding individual ,  greedy strategy ,  repair and optimization

分類 (1件)： 人工知能  (JE08000Z)

タイトルに関連する用語 (3件)： 遺伝的アルゴリズム ,  ナップサック問題 ,  研究