2003 年 1 月 11 日
分散遺伝的アルゴリズム ga2k（ver. 1.４）仕様書
同志社大学工学部 知的システムデザイン研究室
廣安知之， 吉田純一， 佐野正樹， 福永隆宏， 片浦哲平， 澤田淳二
目次
目次 ...................................................................................................................................... 2
1.
はじめに ........................................................................................................................ 3
2.
プログラムの使用方法................................................................................................... 3
2.1.
コンパイルとプログラムの実行 ............................................................................. 4
2.2.
標準のパラメータ................................................................................................... 5
2.3.
コマンドラインオプション .................................................................................... 6
2.4.
性能の評価 ............................................................................................................. 7
3.
分散遺伝的アルゴリズム概説 ...................................................................................... 10
4.
プログラム詳説 ........................................................................................................... 11
5.
6.
4.1.
個体の表現（Gene クラス） ................................................................................ 11
4.2.
島の表現（Island クラス）.................................................................................. 12
4.3.
母集団の表現（Globe クラス）............................................................................ 14
4.4.
初期化................................................................................................................... 15
4.5.
GA の実行 ............................................................................................................ 17
4.6.
選択 ...................................................................................................................... 17
4.7.
移住 ...................................................................................................................... 20
4.8.
交叉 ...................................................................................................................... 22
4.9.
突然変異 ............................................................................................................... 23
4.10.
評価................................................................................................................... 23
4.11.
エリート保存 .................................................................................................... 24
4.12.
終了判定 ........................................................................................................... 25
4.13.
関数の呼び出し関係.......................................................................................... 26
4.14.
関数リスト........................................................................................................ 27
対象問題インターフェース.......................................................................................... 29
5.1.
対象問題インターフェースの構成........................................................................ 29
5.2.
対象問題インターフェースの使用........................................................................ 30
5.3.
対象問題インターフェース（ObjectiveProblem クラス） .................................. 30
離散問題への適用例 .................................................................................................... 32
6.1.
巡回セールスマン問題.......................................................................................... 33
6.2.
トラス構造物最適化 ............................................................................................. 35
参考文献 ............................................................................................................................. 38
更新履歴 ............................................................................................................................. 39
Copyright ........................................................................................................................... 42
2
1. はじめに
本ドキュメントは同志社大学工学部知識工学科知的システムデザイン研究室1が開発した分
散遺伝的アルゴリズムプログラム ga2k の使用方法と仕様についてまとめたものである．こ
のプログラムは，知的システムデザイン研究室の分散 GA 研究グループのサイト2からダウ
ンロードすることが可能である．本ドキュメントは大きく以下のような構成になっている．
まず，次章でプログラムの実行方法とテスト関数における性能について述べる．3 章では分
散 GA のアルゴリズムの概説を行い，4 章ではプログラムの仕様をまとめる．5 章では ga2k
を任意の対象問題に適用するためのインターフェースについて説明する． 6 章では離散問
題への適用例を説明する．
2. プログラムの使用方法
ダウンロードしたファイルを展開すると，以下のファイルが生成される．
ga2k.cpp
ga2k.h
ga2k_main.cpp
ga2k_mpi.cpp
ga2k_mpi.h
ga2k_main_mpi.cpp
function.cpp
function.h
mtrand.cpp
mtrand.h
randring.h
interface.cpp
interface.h
interface_template.cpp
interface_template.h
params_rastrigin.ini
configure
Makefile.in
stamp-h.in
1
2
http://is.doshisha.ac.jp/
http://mikilab.doshisha.ac.jp/dia/research/pdga/
3
aclocal.m4
config.h.in
depcomp
install-sh
missing
mkinstalldirs
autogen.sh
configure.ac
Makefile.am
Makefile.cygwin
design_variable.ini
CHANGES.txt
ファイルを展開するためには以下のコマンドをタイプする．
$ tar xvzf ga2k.tar.gz
2.1.
コンパイルとプログラムの実行
ここでは，make を利用したコンパイルの方法を述べる．プログラムをコンパイルするため
には，まず，configure スクリプトを実行する．configure スクリプトを実行すること
により，Makefile が作成される．
$ ./configure
コンパイラを変更する場合は，CXX=使用するコンパイラを，コンパイルオプションを変更
する場合は，CXXFLAGS=コンパイルオプションをコマンドラインで指定し，以下のよう
に configure スクリプトを実行する．なお，=の前後に空白を入れてはいけない．
$ CXXFLAGS=”-O2 -funroll-loops” ./configure
Makefile を作成したら，以下の要領で make を実行する．
$ make
Cygwin では，configure の実行に失敗することがあるので，失敗した場合は付属の
Makefile.cygwin を使用してコンパイルを行う．
$ make –f Makefile.cygwin
なお，make を使用しない場合にも，以下のコマンドをタイプすることでコンパイルが可能
である．
4
$ g++ -o ga2k ga2k.cpp ga2k_main.cpp mtrand.cpp interface.cpp
make に成功すると ga2k（Windows では ga2k.exe）という実行ファイルが生成される．
これを実行すると標準の設定で分散 GA が実行される．
$ ./ga2k
このプログラムは以下の環境で動作確認を行っている．
実行環境
・ gcc version 2.95.3-5 (cygwin special)
Windows 2000
・ gcc version 2.95.4 20010319 (Debian prerelease)
Debian GNU/Linux (kernel 2.2.18pre21)
コンパイルオプション
・(無し)
・-O2 -funroll-loops
・-O6 -mcpu=pentiumpro -ffast-math -funroll-all-loops
2.2.
標準のパラメータ
一般的な GA においては以下のようなパラメータが存在する．
母集団サイズ（Population size）
最大世代数（Maximum generation）
交叉率（Crossover rate）
交叉法（Crossover method）
突然変異率（Mutation rate）
選択手法（Selection method）
エリート個体数（Number of elite individuals）
また，分散 GA に固有のパラメータには次のようなものがある．
島数（Numver of islands）
移住率（Migration rate）
移住間隔（Migration interval）
5
分散 GA の解探索能力はこれらのパラメータによって変化することが知られているが，一
般のユーザが任意の問題について最適なパラメータ設定を行うことは困難である．ga2k で
は，これらのパラメータのデフォルト値を以下のように設定した．
母集団サイズ（100）
最大世代数
（100）
交叉率（1.0）
交叉法（2 点交叉）
突然変異率（1/染色体長）
選択手法（トーナメント選択，トーナメントサイズ=4）
エリート個体数（5）
島数（各島の個体数を 10 とするため，島数＝母集団サイズ/10）
移住率（0.5）
移住間隔（5）
これらの値は複数のテスト関数における大規模な数値実験の結果から，任意の対象問題に
対して良好な性能を示すと推定された値である．チューニングに関する詳細は文献[1]を参
照されたい．なお，パラメータの値は実行時にコマンドラインオプションで変更すること
ができる．
2.3.
コマンドラインオプション
ga2k には以下のコマンドラインオプションが存在する．オプションを指定して実行する際
は以下のようにタイプする．
$ ./ga2k g100
p（サブ母集団サイズ）：１島あたりの母集団数を整数で指定
i（島数）
：島の数を整数で指定
P（母集団サイズ）
：母集団サイズを 10 の倍数で指定する
（p，i との併用はできない．このとき 1 島あたりの個体数は 10）
e（エリートの数）
：1 島あたりのエリートの数
D（次元）
：対象問題の次元
S（初期個体）
：初期個体の発生法 (0 ランダム
g（最大世代数）
：最大世代数を整数で指定
c（交叉率）
：交叉率を 0 から 1 の実数で指定
m（突然変異率）
：突然変異率を 0 から 1 の実数で指定
6
1 ファイルから読み込み)
s（選択手法）
：0 トーナメント選択（デフォルト）
M（移住率）
：移住率を 0 から 0.5 の実数で指定
I（移住間隔）
：移住間隔を整数で指定
1 ルーレット選択
プログラムの動作確認のために，いくつかのオプションを実装している．
f（テスト関数）：
※Onemax 以外は，各変数は 10bit，10 変数．Onemax は 10bit．
0: Rastrigin
1: Schwefel
2: Griewank
3: Rosenbrock
4: Ridge
5: Onemax
o（適合度の推移の表示）：探索終了後に世代ごとの適合度の推移を標準出力に出力．
z（試行回数）：GA の性能評価は複数試行（20 試行程度）の平均値で行うのが一般的であ
る．o オプションと併用した場合には平均値が出力される．
2.4.
性能の評価
Rastrigin，Schwefel，Griewank 関数における本プログラムの性能を，GENEsYs3[2]と比
較する．適合度の推移を図 1∼図 3 に示す．母集団サイズは 400 個体とした場合の 20 試
行の平均値である．いずれの関数でも GENEsYs より高速に高品質な解が得られているこ
とが分かる．
Back によって開発された汎用 GA ソフトウェア．Grefenstete によって開発された genesis
に独自の機能拡張を加えたものである．
3
7
0.00E+00
Evaluation value
-5.00E-01
-1.00E+00
-1.50E+00
-2.00E+00
GENEsYs
-2.50E+00
DGA
-3.00E+00
0
20000
40000
60000
80000
100000
120000
140000
160000
Number of evaluations
図 1
適合度の推移（Rastrigin 関数）
8
180000
200000
0.00E+00
Evaluation value
-5.00E-01
-1.00E+00
-1.50E+00
GENEsYs
DGA
-2.00E+00
0
20000
40000
60000
80000
100000
120000
140000
160000
180000
200000
Number of evaluations
図 2
適合度の推移（Griewank 関数）
0.00E+00
Evaluation value
-5.00E-01
-1.00E+00
-1.50E+00
-2.00E+00
GENEsYs
-2.50E+00
DGA
-3.00E+00
0
20000
40000
60000
80000
100000
120000
140000
Number of evaluations
図 3
適合度の推移（Schwefel 関数）
9
160000
180000
200000
3. 分散遺伝的アルゴリズム概説
遺伝的アルゴリズム(GA)[3,4]では，探索空間上の探索点を生物の個体とみなす．各個体に
は環境に対する適合度(fitness)が設定される．目的関数(objective function)の値が最適値に
近い個体ほど適合度が高い．適合度の値を計算することを評価(evaluation)という．また，
各個体は設計変数値に対応した染色体(chromosome)を持つ．染色体は{0,1}のビット(遺伝
子)列で表現される．染色体上における各遺伝子の位置を遺伝子座(locus)という．GA にお
ける個体の操作は，対応する設計変数値をコード化(coding)した染色体に対して行う．個体
の適合度を評価する際には，染色体から設計変数値へのデコード(decode)が行われる．染色
体のビット列を遺伝子型 (genotype) といい，それに対して元の設計変数値は表現型
(phenotype) と呼ばれる．
個体の母集団(population)に対して，適合度の高い個体の割合を増加させる選択(selection)，
個体間で染色体の一部を交換する交叉(crossover)，染色体の一部を変更する突然変異
(mutation)，という遺伝的オペレータ(genetic operator)を繰り返し適用する．これによっ
て母集団全体の適合度が向上し，最終的に最適解(optimal solution)に到達することが期待
される．また，性能向上のために各世代の良好な個体を保存する．これをエリート保存
(elitism)という．なお，遺伝的オペレータの繰り返し単位を世代(generation)という．
本プログラムで採用している分散 GA[5]では，母集団をいくつかの島(island)に分割し，島
ごとに GA を実行する．また，島間で個体の交換(移住, migration)を行う．分散 GA の概念
図と流れ図を図 4 に示す．
10
目的関数 f(x)
初期化
移住
交叉
設計変数 x
個体
突然変異
評価
島1
エリート保存
選択
島0
終了
判定
移住
終了
島2
母集団
図 4
分散遺伝的アルゴリズムの概念図と流れ図
4. プログラム詳説
本章では，前章で述べたアルゴリズムに沿って実装されたプログラムについて解説する．
このプログラムは，C++言語で記述されており，３つのクラスからなる．各個体に関する処
理を行う Gene クラス，各島内の処理を行う Island クラス，そして母集団全体を統括す
る Globe クラスである．これらのクラスに実装された変数・関数とその役割について図 4
のフローチャートの流れに沿って解説を進める．
4.1.
個体の表現（Gene クラス）
クラス名
Gene
内容
個体を表現
メンバ変数
vector<char> bitString
染色体
double fitness
適合度
operator<(const Gene& gene)
個体の適合度の比較
initialize(int geneLength)
染色体をランダムに初期化
initialize(int geneLength,
ビットの値を指定して染色体を
char value)
初期化
メンバ関数
11
initialize(int geneLength,
const vector<char>& code)
visualize()
染色体を出力
ga2k.h
場所
個体は，Gene クラス によって表現される．適合度はメンバ変数 fitness に格納される．個
体は設計変数値に対応した{0,1}のビット列(染色体)を持ち，これはメンバ変数 bitString[ ]
に格納される．bitString[]の各要素が遺伝子であり，添え字は遺伝子座を示す．個体の表現
とコード化の概念図を図 5 に示す．適合度計算や染色体のコード化の方法については後述
する．
Gene クラスでは，適合度比較のための関数や，染色体をランダムに設定する関数が定義さ
れている．
母集団
個体
染色体
bitString[ ]
0
1
0
1
1
0
デコード
設計変数
(2次元の場合)
探索空間
5
7
(5, 7)
x2
x1
図 5
4.2.
個体の表現とコード化
島の表現（Island クラス）
12
コード化
クラス名
Island
内容
島の環境を表現
メンバ変数
int populationSize
島の個体数
double crossoverRate
交叉率
double mutationRate
突然変異率
int numElite
エリート数
double mugrationRate
移住率
int migrantSize
移住個体
int nativeSize
個体数−移住個体数
int tournamentSize
トーナメントサイズ
int geneLength
１個体の遺伝子長
int variableLength
１設計変数の遺伝子長
int numVariable
設計変数
double openMax
制約条件の最大値
double closeMin
制約条件の最小値
double delta
設計変数の精度
double finValue
終了条件
FunctionType functionType
目的関数の種類
int type0fEncode
エンコード方法
int numCrossoverPoint
交叉点数
mutable int numEvaluate
島ごとの評価計算回数
SelectionType
選択手法の種類
selectionType
double bestFitness
最大適合度
vector<double> roulette
ルーレット選択を行うための配
列
vector<int> crossoverTable
交叉の際に利用する配列
vector<Gene> gene
遺伝子を格納する配列
vector<Gene> migrant
移住個体を格納する配列
vector<Gene> elite
エリート個体を格納する配列
vector<Gene> newGeneration
選択で選ばれた新しい世代の個
体を格納する配列
メンバ関数
initialize(ifstream& fin)
島の基本設定
immigrate()
移住操作を行う
crossover()
nPointCrossover を呼ぶ
13
nPointCrossover()
n 点交叉を行う
mutate()
突然変異を行う
evaluate()
個体の評価を行う
reproduce()
次世代への個体の置き換えを行
う．
tournamentSelection()
トーナメント選択を行う
rouletteSelection()
ルーレット選択を行う
elitePreservation()
エリートを保存する．
fitness()
適合度を計算する
ga2k.h
場所
Island クラスは島内の個体群(エリート個体含む)と各種パラメータを格納する，また，
島内で実行される遺伝的オペレータ(交叉，突然変異，選択)を定義する．
4.3.
母集団の表現（Globe クラス）
クラス名
Globe
内容
母集団全体を表現
メンバ変数
vector<Island> island
島
Island island_0
全ての島のひな形
int generation
世代数
int maxGeneration
最大世代数
int convGeneration
終了世代数
int migirationInterval
移住間隔
int numIsland
島数
int populationSize
島内の個体数
int totalPopulationSize
全個体数
int migirantSize
移住個体数
int nativeSize
島内の移住しない個体数
int fInitialPopulation
初期個体の発生法
double maxFitness
最大適合度
int maxTrial
試行回数
double sumMaxFitness
全試行の最大適合度の和
int sumGeneration
全試行の終了世代数の和
int numConvergent
最適解探索回数
int totalEvaluate
全島の評価計算回数の和
14
int SumTotalEvaluate
全試行の評価計算回数
vector<double> sumFitness
各世代の適合度のログ
Gene elite
エリート個体
bool fStop
終了条件を満たしたときのその
後の処理
メンバ関数
bool fConv
終了判定
bool fTotalPopsize
未使用
bool fOutput
結果の出力の有無
void initialize()
defalt パラメータの設定
void initialize(int argc,
実行オプションの設定
char *argv[])
void reviseParameters()
パラメータの補正
void establish()
各島の基本設定
void emigrant()
移住する島の決定し，移住個体を
移住する
void execute()
移住間隔ごとに島間で移住を行
い，各島で交叉，突然変異，評価，
エリート保存，選択をし，終了判
定を行う
void showParameters()
パラメータを出力する
void finalize(bool b)
終了後の処理
ga2k.h
場所
Globe クラスは，Island クラスで定義された複数の島を統括している．また島間で行わ
れるオペレータである移住（emigrant()）は，このクラスで定義されている．終了世代
数（maxGeneration）まで execute()関数を実行し，遺伝的オペレータを各島ごとで繰
り返す．
4.4.
初期化
関数名
Gene::initialize()
内容
｛0,1｝のビット列で表現された染色体をランダムに生成．各染色体の
適合度を-DBL_MAX で初期化．
引数
int geneLength
戻り値
なし
場所
ga2k.cpp
15
染色体長
関数名
Island::initialize()
内容
島を初期化する
引数
ifstream& fin
戻り値
なし
場所
ga2k.cpp
初期個体の設計変数値ファイル
各島の初期化は，Island::initialize によって行われる．この関数は島内の個体
(gene[
]) ， 移 住 個 体 (migrant[
]) ， エ リ ー ト 個 体 (elite[
]) を
Gene::initialize()により初期化する．また次の世代に選択された個体群を格納する配
列 newGeneneration[ ]の各要素も Gene::initialize()により初期化する．交叉点
を決定するために用いる配列 crossoverTable[ ]に要素番号を設定する．
デ フ ォ ル ト で は ， Island::Initialize() に お い て ， 島 内 の 各 個 体 の 染 色 体
(Gene::bitString[]) にはランダムに決定された {0,1} のビット列が設定される.
しかし，入力ストリーム
(fin) に フ ァ イ ル が 設 定 さ れ て い る 場 合 に は ，
Island::setGeneFromFile() 関数が呼ばれ，ファイル(design_variable.ini)に
記 述 さ れ た 設 計 変 数 値 を 元 に 個 体 の 染 色 体 を 初 期 化 す る .
Island::setGeneFromFile()では，まず，設計変数値が制約条件を満たしているかど
うかを判定する．制約条件外の数値は，[closedMin openMax]の範囲内に引き戻す．次
に，実数である設計変数値を整数値に変換し，gray_code() 関数によってビット列にコ
ード化する．得られたビット列を個体の染色体として採用する．
関数名
gray_code()
内容
整数値をグレイコードに変換する
引数
vector<char>& bitString
コードを格納する配列(戻り値)
int startPoint
配列の開始点
int bitLength
コードの長さ
int num
変換元の整数値
戻り値
なし
場所
ga2k.cpp
関数名
Gene::initialize()
16
内容
引数に指定されたビット列で染色体を初期化．各染色体の適合度を
-DBL_MAX で初期化．
引数
int geneLength
染色体長
const vector<char>& code
染色体に設定するビット列
戻り値
なし
場所
ga2k.cpp
関数名
Island::setGeneFromFile()
内容
各個体の染色体を，ファイルから読み込んだ設計変数値を元に設定す
る．
引数
ifstream& fin
戻り値
なし
場所
ga2k.cpp
4.5.
ファイル入力用 ストリーム
GA の実行
関数名
Globe::execute()
内容
GA による解探索の主ルーチン．選択，移住，交叉，突然変異，評価，
エリート保存，終了判定を行う．
引数
なし
戻り値
なし
場所
ga2k.cpp
遺伝的オペレータを maxGeneration 回繰り返す．また，移住間隔（migrationInterval）
ごとに，各島の間で移住（Island::immigrate()）を行う．この中で行われる遺伝的操
作はそれぞれ次のような関数に対応している．選択：Island::reproduce()，移住：
Globe::emigrate()， 交叉 ：Island::crossover()， 突然変異 ：Island::mutae()， 評価 ：
Island::evaluate()，エリート保存：Island::elitePreservation()
4.6.
選択
関数名
Island::reproduce()
内容
選択を行う
引数
なし
17
戻り値
なし
場所
ga2k.cpp
Island::reproduce() では，以下に示す選択手法の中から，適切な手法を選び，選択を
実行する．
関数名
Island::tournamentSelection()
内容
トーナメント選択を行う． トーナメント選択では，トーナメントサイ
ズ分の個体をランダムに選び，その中の最良個体を選択することを繰り
返す．
引数
なし
戻り値
なし
場所
ga2k.cpp
配列 tournament[tournamentSize]に gene[populationSize+numElite]から復元
抽出によって個体を格納する．そして tournament[tournamentSize]に対しソートを行
い，適合度の最も高い個体を newGeneration[populationSize]配列に格納する．この
操作を populationSize 回繰り返すことによって，populationSize+numElite 個の
個体から重複を許して populationSize 個の個体を選択する（図 6）．
Island::gene[populationSize+numElite]
tounamentSize個の個体を
格納(復元抽出)
populationSize回実行
vector<Gene>tournament
Island::newGeneration[populationSize]
図 6 トーナメント選択
18
適合度の最も高い
個体を選択
関数名
Island::rouletteSelection()
内容
ルーレット選択を行う．ルーレット選択では，各個体は，適合度に比例
した数だけ生き残る．
引数
なし
戻り値
なし
場所
ga2k.cpp
まず， Island::gene[] の各個体の適合度 （fitness）の最低値（min_fit）を求め
る．各個体の適合度から min_fit を引いたものを選択に用いる適合度とする．この値を用
いて，ルーレット Island::roulette[gene.size()]を作成する．また，適合度の総和
を sum_of_fitness に格納する．
[0
sum_of_fitness] の 範 囲 の 実 数 乱 数 を 発 生 さ せ ， ル ー レ ッ ト
Island::roulette[] 上の位置を特定する． その位置に従って生き残る個体を決定し，
Island::newGeneration[] に 格 納 し て い く （ 図 7 ）． こ の 操 作 を ， Island::
newGeneration.size()だけ繰り返す．
Island::gene[]
roulette[]は，各個体の適
合度に応じた幅のルーレットと
なる．
vector<double>
Island::roulette
乱数で，位置を決定して，
newGeneration[]に追
加する．
この操作を繰り返す．
Island::newGeneration[]
図 7 ルーレット選択
19
4.7.
移住
関数名
Globe::emigrate()
内容
移住トポロジーが１つのリングを形成するように移住先の島を決定し，
移住個体を migrant[ ]に格納する．
引数
なし
戻り値
なし
場所
ga2k.cpp
RandomRing 型の配列 distination[numisland]に移住先を格納する．移住トポロジは
リング型であり，リングは移住ごとにランダムに決定される．送信元は配列の添え字，受
信先は配列の値となる．図 8 において，distination[0]には島 0 の送信先（島 1）が格
納されている．
移住個体はランダムに決定される．移住個体として選ばれた migrantSize 個の個体を移
住先の Island::migrant[migrantSize]配列にコピーする（図 9-(1)）．
関数名
Island::immigrate()
内容
移住個体を島内の個体群に追加する．
引数
なし
戻り値
なし
場所
ga2k.cpp
gene[ ] 配 列 を nativeSize(populationSize-migrantSize) で リ サ イ ズ す る ．
Globe::emigrate()で移住させる個体と，リサイズによって失われる個体はまったく同
じであるため，島全体で見たときには個体に変化は起こっていない．リサイズの後に，
migrant[migrantSize]に格納されている移住個体を島内の個体群 gene[]に追加する．
（図 9-(2)）．
送信元(配列の添え字)
RandomRing distnation(numIsland)
(numIsland = 4 の場合)
0
1
2
3
1
3
0
2
受信先（配列の値）
図 8
RandomRing オブジェクトにによる移住先の決定
20
（1）Globe::emigrate()
island[ n ]
island[ destination[n] ]
migrant
[migrantSize]
gene[populationSize]
ランダムに選択したmigrantSize個の
個体をコピー
（Globe::emigrate）
（2）Island::imigrate()
gene[]をnativeSize個
にリサイズ
移住した個体以外が残る
gene[nativeSize]にmigrant
[migrantSize]を追加する
図 9
移住の実装
21
4.8.
交叉
関数名
Island::crossover()
内容
ｎ点交叉 nPointCrossover()を呼ぶ．
引数
なし
戻り値
なし
場所
ga2k.cpp
関数名
Island::nPointCrossover()
内容
遺伝子の n 箇所に交叉点を設定し，交叉点で２個体の遺伝子情報を交換
する．
引数
なし
戻り値
なし
場所
ga2k.cpp
交叉率 Island::crossoverRate の割合で Island::gene[ ] から交叉する 2 個体を
選ぶ．交叉する個体は重複しないようにする．そして事前に設定された交叉する点の個数
（numCrossoverPoint）から，その長さの配列（crossoverPoint[ ]）を定め，その
配列に交叉するビット列の配列番号をランダムに代入し，交叉点を決定する．なお，
numCrossoverPoint は 2 とする．そして 2 つの染色体 Gene::bitString[ ]の交叉点
以降のビット列を入れ換える．
島
sima
交叉点
ランダムに親個体を決定
0
1
0
1
1
0
0
1
1
0
0
0
1
1
1
0
0
0
0
1
0
1
1
0
交叉前
図 10 交叉（2 点交叉）
22
交叉後
4.9.
突然変異
関数名
Island::mutate()
内容
突然変異を行う．
引数
なし
戻り値
なし
場所
ga2k.cpp
Island::gene[ ] の全ての個体について，突然変異率 Island::mutationRate の割
合で，染色体 Gene::bitString[ ] を走査し，ビットを反転する（図 11）．
確率 Island::mutationRate で，
ビット反転
突然変異前
0
1
0
1
1
0
突然変異後
0
1
0
0
1
0
図 11 突然変異
4.10. 評価
関数名
Island::evaluate()
内容
島内の全ての個体の適合度を計算する．
引数
なし
戻り値
なし
場所
ga2k.cpp
関数名
Island::fitness()
内容
引数で渡された個体の適合度を計算する．
引数
const Gene& gene
戻り値
なし
場所
ga2k.cpp
23
評価対象の個体
Island::gene[ ] の全ての個体についての評価を行う．全ての個体（ビット列）に対し
て ， fitness() 関 数 を 実 行 し ， 適 合 度 値 ( 目 的 関 数 値 ) を 評 価 す る ． 評 価 値 は
Island::gene[i].fitness に格納される．
fitness()関数ではグレイコーディングされたビット列を実数値に変換（デコード）する
必要がある．下の関数で整数値にデコードし，その整数値を[closedMin, openMax)の範囲
の実数値に変換する．
関数名
gray_decode()
内容
グレイコーディングされたものを整数値に変換
引数
vector<char> bitString
染色体
int startPoint
デコードの開始点
int bitLength
遺伝子長
戻り値
int
デコードされた整数値
場所
ga2k.cpp
4.11. エリート保存
関数名
Island::elitePreservation()
内容
エリートを保存する．１世代前のエリートと現在のエリートを比較して
適合度の高い個体をエリートとする．島のサイズは一時的にエリート個
体数分だけ増加する．
引数
なし
戻り値
なし
場所
ga2k.cpp
[１]１世代前のエリート (elite) を temp[] に保存し，現在の個体をソートし適合度
(fitness)の高い個体から順に numElite 個 temp[]に追加する．
[２] [１]で作成した temp[]をソートして，適合度の高い個体から順に numElite 個を
新たにエリート個体として保存する．
[ ３ ] 選 択 の 前 に gene[populationSize] に elite[] を 加 え ， 個 体 数 は 一 時 的 に
populationSize+ numElite となる．
24
Island::gene[populationSize]
Island::elite[numElite]
[１]
適合度の高い上位
numElite個体を格納
numElite個体をその
ままtempに格納
[１]
tmp[numElite + numElite]
適合度の高い個体をエ
リートとする
[２]
[３]
上位numElite
Island::elite
[numElite]
Island::gene[numElite+numElite]
[３]
選択の前にgene[populationSize]にeliteを加える
fitness
Good
Bad
図 12 エリート保存
4.12. 終了判定
終了判定には 2 種類の場合を想定している．一つ目は母集団内の最高評価値があらかじめ
定められたしきい値
island_0.finValue
に達した場合である．二つ目は最大世代数
maxGeneration に達した場合である．終了判定が受理された場合，finalize()によっ
て，探索結果の出力などの処理を行う．
関数名
Globe::finalize()
内容
終了後の処理
引数
bool b
最適解が発見されたときは
真，最大世代数に達したとき
は偽とする
戻り値
なし
場所
ga2k.cpp
25
4.13. 関数の呼び出し関係
void Island :: initialize(int id, char numEnv)
gene.initialize()
migrant.initialize()
elite.initialize()
newGeneration.initialize()
void Island :: crossover()
nPointCrossover()
void Island :: evaluate()
fitness()
void Island :: reproduce()
tournamentSelection()
rouletteSelection()
void Island :: fitness()
gray_decode()
binary_decode()
void Globe :: initialize(int argc, char *argc[])
initialize()
reviseParameters()
void Globe :: establish()
island.initialize(i, island.size())
void Globe :: emigrate()
radomring.shuffle()
26
void Globe :: execute()
island.reproduce()
emigrate()
island.crossover()
island.mutate()
island.evaluate()
island.elitePreservation()
finalize()
4.14. 関数リスト
■ ga2k.cpp
static int gray_decode(const vector<char>bitString, int startPoint, int bitLength)
static int binary_decodee(const vector<char>bitString, int startPoint, int bitLength)
[class Gene]
Gene::Gene()
Gene::~Gene()
void Gene::initialize(int geneLength)
void Gene::initialize(int geneLength, char value)
void Gene::visualize()
bool Gene::operator<(const Gene& gene)
[class Island]
Island::Island()
Island::~Island()
void Island::initialize(int id, int numEnv)
void Island::immigrant()
void Island::crossover()
void Island::nPointCrossover()
void Island::mutate()
27
void Island::evaluate()
void Island::elitePreservation()
void Island::reproduce()
void Island::tournamentSelection()
void Island::rouletteSelection()
void Island::fitness(const Gene& gene) const
[class Globe]
Globe::Globe()
Globe::~Globe()
void Globe::initialize()
void Globe::initialize(int argc, char *argc[])
void Globe::reviseParameters()
void Globe::establish()
void Globe::emigrate()
void Globe::execute()
void Globe::finalize(bool b)
void Globe::showrameters()
■ mtrand.cpp
void sgenrand(unsigned long seed)
double genrand()
int genrand_int(int n)
28
5. 対象問題インターフェース
ga2k は，任意の対象問題に適用するためのインターフェースを持っている．ユーザは，イ
ンターフェース用に用意されたクラスに必要な処理を書き込むことで，ga2k を利用した最
適化を実行できる．
5.1.
対象問題インターフェースの構成
対象問題インターフェースは，ObjectiveProblem クラスによって実装される．以下の 5 つ
のメンバ関数を定義することにより，任意の対象問題の最適化に ga2k を利用することがで
きる．
対象問題の初期化処理 ( initialize() )
この関数は，プログラムの開始時に実行される．対象問題を計算するためにパラメータを
読み込む，メモリを確保するなどの処理が必要な場合は，この関数中に記述する．
遺伝子のデコード ( decode() )
この関数は，個体の評価計算を行う際に実行される．この関数では，0, 1 の遺伝子で表現さ
れた染色体をデコードし，設計変数へ変換する処理を記述する．
解析計算 ( evaluate() )
この関数は，個体の評価計算を行う際に実行される．この関数では，与えられた設計変数
を使って，外部の Analyzer を呼び出す処理を記述する．
適合度計算 ( result_to_fitness() )
この関数は，個体の評価計算を行う際に実行される．この関数では，得られた解析結果か
ら適合度を計算する処理を記述する．
対象問題の終了処理 ( finalize() )
この関数では，プログラムの終了時に実行される．ga2k を終了する際に，一時ファイルを
消去する，確保したメモリを開放するといった処理をする必要がある場合，この関数に記
述する．
各関数がフローチャート中のどこで呼ばれるかを図 13 に示す．
29
初期化処理関数
初期化
デコード関数
解析計算関数
適合度計算関数
評価
エリート保存
選択
移住
交叉
突然変異
終了
判定
終了
図 13
5.2.
終了処理関数
ga2k の処理と関数呼び出しの関係
対象問題インターフェースの使用
5.1 の関数を記述したのち，make を実行し，インターフェースのコンパイルを行う．
対象問題インターフェースを使用する場合は，次のように，コマンドラインオプションと
して，f99 を指定する．
$ ./ga2k f99
本パッケージに付属している interface.cpp，interface.h は，Rastrigin 関数のサン
プルである．
5.3.
対象問題インターフェース（ObjectiveProblem クラス）
クラス名
ObjectiveProblem
内容
対象問題を記述
メンバ関数
void initialize()
初期化処理を行う
void finalize()
終了処理を行う
vector<double>
decode(const
染色体のデコードを行う
vector<char>& chrom)
vector<double> evaluate(const
vector<double>& x)
30
評価計算を行う
double
適合度を計算する
result_to_fitness(const
vector<double>& result)
場所
char* problemName()
対象問題の名前を返す
int numVariable()
設計変数の数を返す
interface.h
5.3.1. 対象問題の初期化処理
関数名
ObjectiveProblem:::initialize()
内容
対象問題の初期化処理を行う
引数
なし
戻り値
なし
場所
interface.cpp
5.3.2. 染色体のデコード
関数名
ObjectiveProblem:::decode()
内容
染色体のデコードを行う
引数
const vector<char>& chrom
染色体のビット列
戻り値
vector<double>
設計変数値
場所
interface.cpp
5.3.3. 解析計算
関数名
ObjectiveProblem:::evaluate()
内容
解析計算を行う
引数
const vector<double>& x
設計変数値
戻り値
vector<double>
解析結果
場所
interface.cpp
5.3.4. 適合度計算
関数名
ObjectiveProblem:::result_to_fitness()
内容
適合度を計算する
31
const
引数
vector<double>&
解析結果
result
戻り値
double
場所
interface.cpp
適合度
5.3.5. 対象問題の終了処理
関数名
ObjectiveProblem:::finialize()
内容
対象問題の終了処理を行う
引数
なし
戻り値
なし
場所
interface.cpp
5.3.6. その他の関数
関数名
ObjectiveProblem:::problemName()
内容
対象問題の名前を返す
引数
なし
戻り値
char*
場所
interface.cpp
関数名
ObjectiveProblem:::numVariable()
内容
設計変数の数を返す
引数
なし
戻り値
int
場所
interface.cpp
対象問題の名前
設計変数の数
6. 離散問題への適用例
GA では，設計変数をコード化した染色体 (ビット列) を用いる．よって，コード化の方法
と遺伝的オペレータを適切に設定すれば，任意の対象問題に適用可能である．
本章では，次の問題を例にとり，離散問題への GA の適用方法について説明する．
巡回セールスマン問題
トラス構造物最適化
32
ここで説明する例はいずれもコード化手法のみを変更するという方法である．遺伝的オペ
レータは，前述のものをそのまま用いることができる．なお，これらの例はあくまで実装
の一例であり，各対象問題に対して十分な性能を実現するためには，コード化手法と遺伝
的オペレータ両方の設計を工夫する必要がある．
6.1.
巡回セールスマン問題
巡回セールスマン問題 (Traveling Salesman Problem : TSP) とは，N 個の点 (都市) と各
点間の距離とが与えられたとき，全ての点をただ 1 度経由する巡回路のうち，巡回路長の
和を最小にするものを求める問題である．図 14 巡回セールスマン問題 は，都市数 N = 7
の場合の TSP の例を示したものである．便宜上，各都市には番号が割り振られているもの
とする．
TSP における解は，都市の巡回順に都市番号を並べた番号列 ( a1 , a 2 , Κ , a N ) で表現する
ことができる．例えば，8 都市の TSP において ，1 → 3 → 5 → 2 → 4 → 7 → 8 → 6
→ 1 の順に都市を巡回する解は，(1, 3 , 5, 2, 4, 7, 8, 6) と表現できる．この番号列から染
色体のビット列へのコード化手法を定義することにより，TSP に GA を適用することが可
能となる．
デコードの方法の例を，図 15 を用いて説明する．都市数 N は 4 とする．まず，都市番号
をビット列で表現する際に必要なビット数は 2 である( 2 = 4 )．よって，解を表現するため
2
に必要な染色体長(ビット列の長さ)は 2×4 = 8 である．都市の巡回順は，次に示すように，
ビット列の左端から決定される．
1. 何らかのデコード手法を用いて，染色体を整数値の列に変換する．
2. 最初の整数値を最初に訪れる都市番号 として確定する．
3. 次の整数値を n とする．確定していない都市番号の集合 C の中から，n 番目のも
のを次の都市番号として確定する．ただし，n が C の要素数よりも大きい場合に
は，mod(n, C の要素数) + 1 を次の都市番号として確定する．ここで，mod(x, y) は
x を y で割った余りである．
4. 3.を繰り返す．
この方法を用いることにより，任意のビット列が実行可能解となり，また，任意の巡回順
に対応するビット列が存在する．
33
都市数 N = 7
都市1 (49, 90)
都市2 (24, 87)
最短巡回路
1→2→4→
6→7→5→
3→1
都市3 (91, 73)
都市4 (25, 50)
都市5 (64, 47)
都市6 (23, 31)
都市7 (75, 15)
染色体 (8ビット)
整数値への写像
図 14
巡回セールスマン問題
1
1
0
2
1
4
1
0
3
0
0
1
{4} の中の mod(1, 1) + 1番目 → 都市 4
{1, 4} の中の mod(3, 2) + 1 番目 → 都市 1
{1, 3, 4} の中の mod(4, 3) + 1 番目 → 都市 3
都市 2
表現型
(巡回順)
( 2, 3, 1, 4 )
図 15
TSP におけるデコードの方法 (都市数 N = 4 の場合)
34
6.2.
トラス構造物最適化
トラス構造物最適化問題は，図 16 に示すようなトラス構造物において，各部材の変形や破
損があらかじめ定められた範囲内に収まるように，総体積を最小化する問題である．トラ
ス構造物を構成する部材には体積や強度によっていくつかの種類があり，部材番号によっ
て識別されるものとする．体積の大きな部材ほど強度が強い．いろいろな部材を組み合わ
せることにより，一定以上の強度を持つ最小体積のトラス構造物を設計する．なお，トラ
スが配置される各部位にも番号が割り振られているものとする．
トラス構造物最適化では，部材の変形や破損に関係する以下のような制約条件がある．
応力 : 各部材にかかる応力を，一定値以下にする．
座屈 : 限界を越える力が加えられることによって起こる部材の変形・破壊 (座屈)
を抑える．
変位 : 力を加えた点の変位を一定値以下にする．変位は接点ごとに計算される．
これらの制約条件に違反する個体 (解) に対する措置としては，適合度にペナルティを付加
する方法や，その個体を致死遺伝子として母集団から削除する方法などが挙げられる．
トラス構造物最適化における解は，どの部位にどの部材が使用されているかを示す番号列
(a1 , a 2 , Κ , a N ) で表現することができる．N は部材の数 (部位の数) である．例えば，部
位 3 に部材 6 が配置されている場合， a 3 = 6 となる．この番号列から染色体のビット列へ
のコード化手法を定義することにより，トラス構造物最適化問題に GA を適用することが
可能となる．
デコードの方法の例を，図 17 を用いて説明する．構造物における部材の数 N は 5，部材の
種類は 4 とする．部材番号をビット列で表現する際に必要なビット数は 2 である( 2 = 4 )．
2
よって，解を表現するために必要な染色体長(ビット列の長さ)は 2×5 = 10 である．染色体
を，何らかのデコード手法を用いて部材番号の列に変換する．この番号列を元に，各制約
条件と構造物の総体積を計算する．
35
力点 (変位)
F
部材の接点
部材
(応力，座屈)
図 16
トラス構造物最適化
36
1
部位番号
0
染色体 (10ビット)
2
1
1
( 2，
部材番号
3
1
4，
1
4
0
3，
0
5
0
1，
10
0
3 )
②
③
①
⑤
図 17
①
②
③
④
⑤
④
部材
部材
部材
部材
部材
2
4
3
１
3
トラス構造物最適化におけるデコード方法 (5 部材の場合)
37
参考文献
[1]
廣安知之，三木光範，上浦二郎：分散遺伝的アルゴリズムにおけるパラメータの検討，
MPS シンポジウム論文集（情報処理学会シンポジウムシリーズ Vol.2001, No.12）,
pp.147-154（2001）
[2]
Thomas Bäck:A User’s Guide to GENEsYs 1.0, University of Dortmund. Software
package documentation（1992）
[3]
J.H.Holland: Adaptation in Natural and Artificial Systems. University of Michigan
Press（1975）
[4]
D.E.Goldberg: Genetic Algorithms in Search Optimization and Machine Learning.
Addison-Wesley（1989）
[5]
Reiko Tanese: Distributed Genetic Algorithms, Proc. 3rd International Conference
on Genetic Algorithms, pp.434-439（1989）
38
更新履歴
■ 2003.1.11
ver. 1.4 ■
2.1 コンパイルとプログラムの実行方法
configure による Makefile の作成方法を追加．
5 対象問題インターフェース
対象問題インターフェースに関する記述を追加．
■ 2002.07.25
ver. 1.3 ■
4.2 島の表現（Island クラス）
Island クラスの表に，以下のメンバ変数を追加
FunctionType functionType;
SelectionType selectionType;
4.3 母集団の表現（Globe クラス）
void Globe::reviseParameters() を追加
4.6 選択
この節の位置を変更
4.13 関数の呼び出し関係
void Island::reproduce()
void Globe::reviseParameters()
を追加
4.14 関数リスト
void Island::reproduce()
void Globe::reviseParameters()
を追加
■ 2002.07.05
ver. 1.2.7 ■
Copyright
39
ライセンスについての条項を修正
■ 2002.07.03
ver. 1.2.6 ■
2.3 コマンドラインオプション
次のコマンドラインオプションを追加
「e（エリートの数）
「D（次元）
：1 島あたりのエリートの数」
：対象問題の次元」
■ 2002.07.01 ver. 1.2.4 ■
4.2 島の表現（Island クラス）
「クラス Island」の表の「メンバ変数」の欄から，以下の項目を削除．
・int islandId
各島の ID
・int numIsland
島数
4.4 初期化
「関数 Island::initialize()」の表の「引数」の欄から，以下の項目を削除．
・int id
・int numEnv
各島の ID
島数
■ 2002.06.04 ver. 1.2 ■
2.3 コマンドラインオプション
次のオプションを追加
「s（選択手法）
：0 トーナメント選択（デフォルト）
1 ルーレット選択」
「f（テスト関数）：
※Onemax 以外は，各変数は 10bit，10 変数．Onemax は 10bit．
・・・（中略）・・・
5: Onemax」
4.2 島の表現（Island クラス）
Island クラスの表に，次のメンバを追加．
「int selectionType
| 選択手法の種類」
「rouletteSelection()
| ルーレット選択を行う」
40
4.11 選択
「Island::reproduce()」の表を追加．
ルーレット選択（Island::rouletteSelection()）の表と，説明を追加．
■ 2002.01.17
ver. 1.1 ■
2.3 コマンドラインオプション
次のコマンドラインオプションを追加．
「 S（初期個体）
：初期個体の発生法 (0 ランダム
1 ファイルから読み込み) 」
4.4 初期化
Island::initialize() の表に，次の引数を追加．
「 ifstream& fin
| 初期個体の設計変数値ファイル 」
本文第 2 段落
「デフォルトでは， ・・・ 個体の染色体として採用する．」
の部分を追加．
以下の 3 つの関数の表を追加．
gray_code()
Gene::initialize()
Island::setGeneFromFile()
■ 2001.12.13
ver. 1.0 ■
ga2k の開発開始
41
Copyright
■ GA2K:
Parallel Genetic Algorithm Team of Intelligent Systems Design Laboratory, Doshisha
University.
Copyright (C) 1999
Ikki Ohmukai,
All rights reserved.
Copyright (C) 1999,2000,2001
Jun-ichi Yoshida,
All rights reserved.
Copyright (C) 2001,2002,2003
Tomoyuki Hiroyasu, All rights reserved.
Copyright (C) 2001,2002,2003
Mitsunori Miki,
All rights reserved.
Copyright (C) 2002
Masaki Sano,
All rights reserved.
Copyright (C) 2002,2003
Junji Sawada,
All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are
permitted provided that the following conditions are met:
1.
Redistributions of source code must retain the above copyright notice, this list of
conditions and the following disclaimer.
2.
Redistributions in binary form must reproduce the above copyright notice, this list
of conditions and the following disclaimer in the documentation and/or other
materials provided with the distribution.
3.
The names of the authors should not be used to endorse or promote products
derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS
OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL
DAMAGES
(INCLUDING,
BUT
NOT
LIMITED
TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
DAMAGE.
42
■ GA2K manual:
Copyright (C) 2001
Teppei Kataura,
All rights reserved.
Copyright (C) 2001
Takahiro Fukunaga,
All rights reserved.
Copyright (C) 2001
Jun-ichi Yoshida,
All rights reserved.
Copyright (C) 2001,2002
Masaki Sano,
All rights reserved.
Copyright (C) 2001,2002,2003
Tomoyuki Hiroyasu,
All rights reserved.
Copyright (C) 2001,2002,2003
Mitsunori Miki,
All rights reserved.
Copyright (C) 2002,2003
Junji Sawada,
All rights reserved.
43
© Copyright 2024 ExpyDoc
