個体数を減少させた実数値遺伝的アルゴリズムに関する調査

福永隆宏, 廣安知之, 三木光範

ISDL Report　 No. 20030502034

2003年 11月 11日

Abstract

本稿では, 実数値遺伝的アルゴリズムにおいて, 少ない個体数での解探索性能について考察する. 今後構築するブレインアシストシステムでは, ユーザインターフェースに携帯電話を用いる. そこで問題となるのは, 表示画面の描画面積の狭さである. 探索個体の情報を可視化する場合, その制約を考慮しなければならない. この問題を解決すべくアプローチはいくつか考えられるが, 本稿では, 探索に用いる個体数を減少させることを指針をした. 交叉法にUNDX, 世代交代モデルにMGGを適用した実数値GAに関して, 一般的に用いられている個体数よりも少ないパラメータで数値実験を行い, 解探索性能を調査した. 様々な性質を持った数学的テスト関数に適用したところ, 対象問題依存であることは否めないが, 最適解を発見するという観点から考察すると, 良好な探索を示す場合も確認できた.

1 はじめに

本稿は, 実数値遺伝的アルゴリズム（Real-coded Genetic Algorithm: RCGA）において, 少ない個体数での解探索性能について考察する. 一般的に報告されているRCGA（UNDX+MGG）の個体数の推奨値は, 単峰性関数の場合は50個体, 多峰性関数の場合は300個体であり, MGGの生成個体数はいずれも200個体となっている. 本稿ではいずれの場合も個体数20としており, 比較的少ない個体数で実験を行った.

2 Brain-Assistシステム

2.1 背景

最適化問題を解く場合, 従来は解空間における探索を計算機で行い, 得られた解に対して, 人間がその精度等の妥当性を経験に基づいて判断し, 必要に応じて修正を加える等の処理を施してきた. しかしながら, 高性能の最適化アルゴリズムを適用しても, 満足できる解を得ることが容易でない問題も多く存在する. こうした場合, 人間の直感に基づく高度な判断と解探索を行う計算機の共同作業が不可欠であると考えられる.

本研究では, コンピュータシミュレーションによる解探索のプロセスに, 人間の直感, 経験に基づいた操作を融合させることを考案する. このようなシミュレーションによる探索に人間が介在し, 解探索を促進する仕組みをブレインアシストと呼ぶことにする.

2.2 研究計画

ある世代における遺伝的操作をGUIを用いて可視化する. GUIで表示されている個体群から. 人間は各個体の遺伝子情報をもとに, 交叉する個体, 突然変異する個体, 及び遺伝子座の位置を選択できるようなシステムを構築する. Fig.1 は, 本システムの概念図を示している.

Fig.1: Brain Assist Systemの概念図

遺伝的操作に人間が介在するためには, GUIを構築する必要がある. 対象問題の最適化は, 遠隔にある計算機で行い, 各個体の遺伝子情報を表示する機器として, 携帯電話またはPDA等の使用を考えている. 携帯電話を用いる理由としては, 計算機と人間を結ぶ利便性の高いユーザインターフェースになることが多いに期待できるからである. しかし, 個体情報を表示する描画領域が一般的なPCと比較して非常に狭いという問題も生じる.

3 個体数の少ないRCGA

3.1 概要

個体数が少ないRCGA(UNDX+MGG)の解探索性能を調査するために, いくつかの数学的テスト関数を用いて検証した. 対象問題はRastrign関数, Schwefel関数, Griewank関数, Rosenbruck関数, Ridge関数, そして最適解の位置をすべての次元において5移動したRastrigin_5関数である. 次元数はそれぞれ5, 10, 20次元としている. また, Table 1 に実験に用いたパラメータを示す.

Table 1: Parameters

パラメータ	値

個体数	20
世代交代モデル	MGG
生成個体数	200
設計変数(n)	5, 10, 20
交叉方法	UNDX
UNDXパラメータ:α, β	α=1.0, β=0.35
突然変異率	0.0, [ 1/n×10]
試行回数	20

3.2 数値実験結果

Fig.2 は, 各関数ごとの平均評価計算回数を示している. 結果は20試行平均である. ここでいう最適解とは, 関数評価値が1.0-E08に達した場合とした.

(a)rastrigin

(b)schwefel

(c)griewank

(d)rosenbrock

(e)ridge

(f)rastrigin_5

Fig.2: results

Tab::@result@ より, Griewank関数を除いて最適解に到達していることが確認できる. 設計変数間に依存関係がなく, 多峰性関数（Fig.2(a) , Fig.2(b) , Fig.2(f) )に注目すると, 突然変異が非常に重要であることがわかる. これは. 個体数が少ないためMGGを適用しても多様性が失われる可能性が高いためであると考えられる. 次に設計変数間に依存関係あり, 単峰性関数（Fig.2(d) , Fig.2(e) ）に注目すると, 突然変異を適用しないほうが良い. これは, 局所最適解が存在しない単峰性関数は, 親の形質を考慮した探索で十分である. しかしながら, 突然変異は親の形質を破壊する可能性が高いのでこのような結果になったものと思われる.

4 まとめ

本稿では, ブレインアシストシステムを考慮した個体数の少ないRCGA（20個体）に関して, その解探索性能を調査した. Greiwank関数のみ良好な性能を示さなかったが, 他の関数においては, その形状によって突然変異操作の有無を考慮することで, 最適解に到達することが期待できる. 必然的に個体数を少なくすると, 解探索における多様性が欠如してしまう. MGGを併用することで多様性維持を図る. また, 多峰性関数に関しては, 突然変異操作を適用するで局所解脱出を図る. さらに, 子個体生成領域を拡大することでも, 幾分か多様性維持を図れるのではないかと考えている.

Copyright

Copyright (C) 2003 Tomoyuki Hiroyasu, All rights reserved.
Copyright (C) 2003 Mitsunori Miki, All rights reserved.
Copyright (C) 2003 Takahiro Fukunaga, All rights reserved.

No part of this document may be reproduced, copied, distributed,
transferred, modified, or transmitted, in any form or by any means,
without the prior written permission of the authors.
In no event shall the authors be liable for any damages caused in any way
out of the use of this document．

File translated from T_EX by T_TH, version 3.40.
On 11 Nov 2003, 15:37.