報告書番号

R99032

タイトル（和文）

遺伝的アルゴリズムによる不確実性をともなう大規模・複雑問題の効率解法 -サンプリング平均で個体を評価するGAの理論的妥当性-

タイトル（英文）

An efficient method based on genetic algorithm (GA) for solving large complex optimization problem with uncertain parameters-Validity of GA in which individuals are evaluated under sampled environments-

概要 （図表や脚注は「報告書全文」に掲載しております）

現実の多くの意思決定は，不確実な情報にもとづいて行われる。したがって意思決定支援を目的とする最適化手法には，入力データの変動に対して頑強な解を見つけ出すことが望まれる。こうした課題に対し当所では昨年度，入力データが複数のシナリオとして与えられる大規模・複雑な問題を効率的に解くアルゴリズムを提案し，これをネットワークを含めた分散型情報システムの最適設計へと適用した。提案アルゴリズムは遺伝的アルゴリズム（GA: Genetic Algorithm）をベースに，ランダムにサンプリングしたシナリオでの平均適応度で個体を評価し，適応度の低い個体についてはサンプリングの早い段階で淘汰することで効率的に解を探索する。本報告では，このアルゴリズムにおいて，全シナリオにおける個体の平均適応度を，ランダムサンプリングした個別シナリオでの平均適応度で推定することの妥当性を，理論面，実験面から検証した。

概要 （英文）

In many actual cases, we have to make a decision by uncertain information. For example, it is impossible to obtain an exact value of the future load, when we design a new computer system. We can only use estimated value of the future load to decide capacity of system elements. Thus, an optimization method, that finds a solution by considering uncertainty of input parameters, is essential to support a decision-making.We have proposed a new efficient algorithm, based on GA, that can solve a large complex problem in which input data are given as different scenarios. The algorithm finds an individual (solution) which maximize an average fitness (Objective function) for the given scenarios. In this paper, we ascertain the validity of the algorithm.The algorithm finds an optimal individual efficiently as follows; (1) sample scenarios from the given scenarios, (2) calculate the fitness of an individual under each sampled scenario, (3) screen individuals whose average fitness is low, (4) evaluate individuals, that gain high average fitness, more precisely by reproducing them to next generation, and evaluating them by additional scenarios. It can be assumed that the average fitness under sampled scenarios is distributed as a normal distribution.Using the property, the algorithm selects the individuals by considering the scattering of the average fitness of an individual under sampled scenarios. Thus, the probability, that an excellent individual is selected, can be restrained in less than a constant value in the algorithm.We apply the algorithm to a stochastic facility location problem, and evaluate the efficiency of the proposed algorithm. We solve the facility location problem with 3 scenarios of future load and cost. In this case, we can obtain a global optimum 35 times when we solve the problem 50 times by proposed algorithm. The CPU time of getting a solution by the proposed algorithm is less than 1/15 of CPU time of obtaining a global optimum. Next, we apply the proposed algorithm to the more difficult problem with 27 scenarios.In this case, we can obtain a good solution efficiently by the proposed algorithm.

報告者

キーワード