Simulated annealing (SA) is a general method to solve combinational optimization problems. SA generates a neighbor solution from a current solution randomly and evaluates the solution by a cost function. If a neighbor solution is better than a current solution, or otherwise stochastically, the neighbor solution is accepted as a new current solution. SA needs long execution time because it must iterate generating and evaluating a neighbor solution many times. We propose a fast SA method where some neighbor solutions are generated at a time in a look-ahead manner and evaluated in parallel. A method to adaptively generate neighbor solutions is proposed to reduce void solutions which are not used in a SA chain.%最適化組み合わせ問題の解を探索するメタヒューリスティックアルゴリズムである焼きなまし法(SA)は,現在の解候補からランダムに近傍解を生成し,評価関数値を比較して改善時,または確率的に近傍解を新たな解候補とする手法であり,近傍解の生成と評価関数計算を多数繰り返すため長い時間を要する.本研究では,SA高速化のため,複数の近傍解を生成し,その評価関数計算を並列に行うことで実行時間の短縮を図る.さらに,単ーチェーンSAの並列化を目的とし,先見的な近傍解の生成パターンを適応的に変化させることで本来到達しない無駄な近傍解の生成数を削減する手法を提案する.
展开▼