2目次

目
はじめに第1部

次11

オブジェクト指向とフレームワーク

Chapter 118

オブジェクト指向理解のポイント … …… 19

1.0

実際の世界をうまく表現できそう

1.1

実体の動的生成21

1.2

継承（階層構造）

23

1.3

メンバ関数

1.4

演算子多重定義

1.5

多態性

1.6

動的束縛

1.7

カプセル化の意味

20

23
24

24
25
27

Chapter 2 C++ 超入門 … ……………………………… 29
2.0

クラスと継承30

2.1

クラスをまとめるクラス

31

3

目次

2.2

継承

31

2.3

クラスとオブジェクト

2.4

オブジェクトの生成と消滅

2.5

継承と初期化

2.6関数のオーバーライド

2.7

オブジェクトのメモリレイアウト

2.8

static なメンバ

2.9

多重継承

40
41

50
52
55

61

66

2.10 演算子オーバーロード

73

2.11 代入と初期設定（コピーコンストラクタの必要性）
2.12 テンプレート

88

93

Chapter 3 オブジェクト指向分析・設計超入門 ……… 97
3.0

UML（Unified Modeling Language）

3.1

クラス図（クラスダイアグラム）

98
98

Chapter 4 フレームワークは快適な乗り物 ………… 109
4.0

オブジェクト指向フレームワーク

110

4

目次

4.1

フレームワークの特色を生むしくみ

110

4.2

フレームワークの構成とデザインパターン

4.3

GA と GP におけるフレームワーク

112

113

Chapter 5 ＧＡフレームワークの構造 ……………… 115
5.0

オブジェクト指向分析・設計

116

5.1

GA クラステンプレート

5.2

フレームワークの動作

5.3

コンソールアプリケーションの外部仕様

5.4コンソールアプリケーションの GA プロセスオブジェクト 129

5.5

GUI アプリケーションの外部仕様

5.6

GUI アプリケーションでの GA プロセスオブジェクト 140

5.7

GUI アプリケーションでの表示オブジェクト

120
127
128

134

151

Chapter 6 ＧＰフレームワークの構造 ……………… 153
6.0

遺伝的プログラミング

6.1

遺伝的プログラミングでの遺伝子表現

6.2

ADF 対応の GP157154156

5

目次

6.3

GP におけるオブジェクト指向分析・設計

6.4

GP クラステンプレート

161

6.5

フレームワークの動作

181

6.6

コンソールアプリケーションの外部仕様

6.7コンソールアプリケーションの GPプロセスオブジェクト 183

6.8

GUI アプリケーションの外部仕様

6.9

GUI アプリケーションでの GPプロセスオブジェクト 188

遺伝的アルゴリズムの応用

181

186

6.10 GUI アプリケーションでの表示オブジェクト

第2部

158

189

190

Chapter 7 どの順序で作ろうか ? … ……………… 191
7.0

生産順序決定問題

192

7.1

問題の定義

7.2

遺伝子コーディング

7.3

主要プログラムの解説

7.4

実行形式の作成

7.5

実行結果

192

203

195

201

197

6

目次

Chapter 8 時間割は奥深い …………………………… 205
8.0

時間割問題

206

8.1

問題の定義

206

8.2

遺伝子コーディング

207

8.3

制約条件の実現方法

209

8.4

データ構造

8.5

主要プログラムの解説

8.6

実行形式の作成

8.7

実行結果

210
212

219

220

Chapter 9 後片づけはむずかしい？！ ……………… 223
9.0

箱詰め問題

224

9.1問題の定義

224

9.2

遺伝子コーディング

9.3

遺伝子コーディングの解釈

9.4

データ構造

9.5

主要プログラムの解説

9.6

実行形式の作成

225
227

229

238

231

7

目次

9.7

実行結果

239

Chapter 10 遊びじゃないスケジュール …………… 244
10.0 ジョブショップスケジューリング問題（JSP）
10.1 問題の定義

246

10.2 遺伝子コーディング
10.3 遺伝子の解釈

247

249

10.4 遺伝的操作

25110.5 クラスタ平均化法
10.6 データ構造

254

256

10.7 主要プログラムの解説
10.8 実行形式の作成
10.9 実行結果

第3部

245

257

263

264

遺伝的プログラミングの応用

268

Chapter 11 まずは多数決をとってみよう ………… 269
11.0 多数決判定問題
11.1 問題の定義

270
2708目次

11.2 関数の登録272

11.3 主要プログラムの解説
11.4 実行形式の作成
11.5 実行結果

273283285

Chapter 12 この次にくる数はなんだろう ………… 287
12.0 数列規則を見出す問題
12.1 問題の定義

288

12.2 関数の登録

29012.3 主要プログラムの解説
12.4 実行形式の作成
12.5 実行結果

288

292300301

Chapter 13 体積の差がわかるかい ………………… 303
13.0 体積差を計算する問題
13.1 問題の定義

304

304

13.2 RPB と ADF の関係

306

13.3 Automatically Defined Function（ADF）

308

9

目次

13.4 関数の登録309

13.5 主要プログラムの解説
13.6 実行形式の作成
13.7 実行結果

Chapter 14311322323

人工蟻を進化させる … ……………… 325

14.0 Santa Fe trail 問題の解法14.1 問題の定義

326

14.2 関数の登録

329

14.3 主要プログラムの解説
14.4 実行形式の作成
14.5 実行結果

Chapter 15326

330338339

倉庫番はつらいかも … ……………… 344

15.0 倉庫番問題の解法
15.1 問題の定義

345

15.2 関数の登録349

15.3 主要プログラムの解説

345351

10

目次

15.4 実行形式の作成
15.5 実行結果

参考文献

367

あとがき

371

索引

362363372

ダウンロードサービスのご利用について
著者略歴／著作権表示／奥付

384383

11

はじめにはじめに進化は何らかの組織がまわりの条件を克服して，いくらかでも優位を保とうとするしくみと考えられます．生物は途方もない時間をかけて，この魅力的なメカニズムを利用し，自らを改良させてきました．このようなメカニズムは，生物の進化だけではなく脳内における意識の形成［Calvin 96］などにも存在しているようです．生物進化の担い手は遺伝子で，生物の設計図といわれてきましたが，生物の隅々まで遺伝子に細かく書き込まれているわけではなく，常に外界との相互作用で形成される場に従っていることがわかってきています．
このような進化のメカニズムをコンピュータ利用の情報処理に応用したのが遺伝的アルゴリズムであり遺伝的プログラミングなのです．コンピュータの中では個体の成長期間を無視し，実際の進化スピードを極端に切りつめて，遺伝子の変化とその評価を中心に行っています．これにより，進化のメカニズムを最適化問題などに応用しているわけです．つまり冒頭に記したように，制約条件を「克服する条件」として扱い，「いくらかでも優位を保とうとするしくみ」が最適性へのベクトルを生み出すことになります．
本書は，欲張って，オブジェクト指向と遺伝的アルゴリズムと遺伝的プログラミングという 3 つをテーマにしています．しかし単に欲張っただけではありません．遺伝的アルゴリズムと遺伝的プログラミングは，ともに進化のメカニズムを利用した最適解を求める方法であり，似ている部分が多いのです．名前からして，それは簡単にわかることでもあります．しかし，これらとオブジェクト指向とが，どう関係するのか．オブジェクト指向とは，システム開発における救世主として 20 年も前に出現した考え方であり，オブジェクト指向言語として具現化したのです．ただ，オブジェクト指向においても，当初喧伝されてきたような再利用性の高さ，拡張の容易さについては，必ずしも期待どおりとはなりませんでした．しかしながら 20 年の間に考え方が進み，今では，随分と改善されているのです．その 1 つが，本書で取り上げているフレームワークというシステムの構成法です．このオブジェクト指向におけるフレームワークという考え方は，特定のドメインにおけるシステムを構築するための有力な方法となっています．特定のドメインを仮定すると，システムの基本となる部

12

はじめに分が共通に括り出せ，ドメイン内における個別の機能要求が，基本部分に付加される構造となります．これを，容易に実現する枠組みがフレームワークと呼ばれるものです．
遺伝的アルゴリズムと遺伝的プログラミングとは，ともに進化のしくみを使って何らかの最適化を行う手法です．それら 2 つの間の共通性までは求めずに，それぞれの領域を分けて考えると，さらに動きを含めて基本的な部分が拡大します．その多くは，それぞれの領域でのアプリケーションに共通的な考え方となっていますから，その共通的な部分をフレームワークとして構成しておくと，それぞれ，各種のアプリケーションに適用する場合，アプリケーションに固有な部分だけを拡張することで対処できるようになります．つまり，核となる部分を固めておき，アプリケーション固有部分を追加できるようにしておくことにより，遺伝的アルゴリズムと遺伝的プログラミングを適用するアプ
リケーションの開発効率を大きく向上させることができます．オブジェクト指向を用いるまでもなく，共通部分ならば共通部品として作っておけば，上述のことは可能ではあります．しかしながら，拡張しても，フレームワーク部分への変更が一切及ばないとしたら別です．オブジェクト指向が提供するしくみは，それを可能にしているのです．さらに，単なる共通部品ではなく，それだけでも遺伝的アルゴリズムと遺伝的プログラミングのシステムとして動かすことができます．もちろん，アプリケーション部を正式には定義していませんので，動きを観察できるだけですが．
以上のようなフレームワークを準備しておくと，何らかの課題を解決しようとするとき，新たにプログラムを作成する部分は，従来の 30 〜 50％ほどです
みます．それもその課題固有の部分だけですので，問題解決に注力できるわけです．
さて，遺伝的アルゴリズムと遺伝的プログラミングのしくみ部分は，フレームワークに任せるとして，これら 2 つの違いについて知っておくべきでしょう．
両者とも，ダーウィンの進化論を基礎においている点では共通です．ともに，集団進化の効果を狙っているわけです．遺伝的アルゴリズムは，個体が持つ遺伝子とそれが配列であるということを利用して，適用する問題の特徴値をそれらに表現します．その個体が進化することで探索や最適解を求めます．一方，

13

はじめに遺伝的プログラミングは，個体の遺伝子にプログラムの断片（正確には関数）を表現し，遺伝子の配列である染色体で目的の機能を果たせるプログラムを表現します．遺伝的アルゴリズムが解そのものを進化させることに対して，遺伝的プログラミングは機能を進化させることになるわけです．
遺伝的プログラミングでは，進化の方向を決めるために事例を用います．つまり学習システムでは一般に教師データと呼んでいて，入力とそれに対してシステムが応答すべき出力を組にしたものです．入力と正しい応答の組を正事
例，誤った応答の組を負事例と呼んでいますが，本書の遺伝的プログラミン
グでは正事例を扱っています．このような教師データを充分な数用意して，進化という学習を行わせて，すべての教師データをうまく説明できるようなプログラムを生み出すようにします．つまり，帰納的推論を行っていることになるわけです．
ただ何の指針もなく帰納的推論を行うことは困難でしょう．述語論理の世界で，同様に正事例から，それを説明可能な述語に合成する研究があります［Shapiro 82］．しかしながら，合成すべき述語の引数の数や，それがアトムなのかリストなのかといったタイプに，何の制限も与えることなく，帰納することはできません．そこでも，それらはあらかじめプロトタイプとして与えています．
遺伝的プログラミングでは，目的の関数を構成する基本的な関数の集合を与えています．それらの関数の働きは，当然ながら正確に規定されています．そのような関数を組み合わせて目的の関数を合成していきます．ここで注意しておかなければならないのは，手続型のプログラミング言語表
現でプログラムを合成するのではなく，LISP などの純粋な関数型として表現するということです．関数型言語の特色は，手続型の代入文や条件文などの制御構造もすべて関数化されています．この特徴が，プログラム合成を容易にしています．遺伝的プログラミングでは，LISP をその処理系として用いている場合が多いのも，そのような理由からです．しかしながら，本書では，C++ を処理系として用い，合成対象のプログラム表現に LISP 流の形式を用いることにしています．
プログラムは，個体の染色体がその構造を表現しています．つまり個体が14はじめにプログラムを作っているわけですから，遺伝子表現には，プログラムの表記レベルのイメージを持たせる必要はまったくありません．いいかえると，コンパイラはソースプログラムを解析して内部表現に変換していますが，その変換後の表現を遺伝子に表現させて，そのレベルで遺伝的操作を施せばいいわけです．
つまり，遺伝的プログラミングの処理中は，内部表現のままで進化を行わせることができるわけです．人間が見てわかるような表層レベルの表現は，必要になったとき変換してやればいいわけです．
遺伝的アルゴリズムに関しては，『応用事例でわかる遺伝的アルゴリズムプログラミング』を同じくパーソナルメディア社から出版しております．本書はその内容と重ならないように工夫しています．したがって，遺伝的アルゴリズムの基礎については，前著を参照していただけると幸いです．

本書の読み方案内
本書は，前述しましたように，オブジェクト指向フレームワークを核として，各アプリケーションを構築しています．また，可能な限り本書のみで済むように，内容理解を助けるためのオブジェクト指向への入門を設けています．
本書は 3 部構成となっていて，第 1 部はオブジェクト指向からフレームワー
クへの展開について説明します．オブジェクト指向についてはその意味から解きほぐし，オブジェクト指向をまったく知らなくても，C++ のプログラムが理解でき，書けるようになることを目指し，次のフレームワークの理解につなげられるようにしています．GA フレームワークと GP フレームワークの解説では，それぞれの特色からフレームワークがどのように構成されるかを解説します．
また，フレームワークは GUI 用とコンソールアプリケーション用を用意しています．
第 2 部は遺伝的アルゴリズムの応用で，GA フレームワークを適用した，4つのアプリケーションについての解説です．次の章から構成されます．

15

はじめに7 どの順序で作ろうか？：巡回セールスマン問題の応用
ひとつの機械に材料を流す最適な順序を決めます．小規模の玩具メーカにおける生産工程を例にして，コンソールアプリケーションとして実現します．
8 時間割は奥深い：時間割問題（Time Tabling Problem）
大学や短大における時間割の作成について，コンソールアプリケーションとして実現します．
9 後片づけはむずかしい？！：箱詰め問題の解法
GUI 系としての応用で，箱詰め問題の GA による解法を実現します．問題の例としては，Tetrix とペントミノをとりあげています．
10 遊びじゃないスケジュール：Job-Shop Scheduling 問題（JSP）の解法
産業界で最も重要なスケジューリング問題のひとつである JSP の解法を解説します．コンソールアプリケーションとして実現します．
第 3 部は遺伝的プログラミングの応用で，GP フレームワークを適用した，5 つのアプリケーションについての解説です．次の章から構成されます．
11 まずは多数決をとってみよう：多数決判定プログラムの合成
少数ビットを対象にし，過半数以上のビットが ON になっているか否かを判定するプログラムを合成します．コンソールアプリケーションとして実現します．
12 この次に来る数はなんだろう：数列規則を見出す問題
1, 2, 4, 7, 11, 16, …, といった，数列の規則をあらわす漸化式を合成するような場合を取り扱います．コンソールアプリケーションとして実現します．
13 体積の差がわかるかい：体積差を計算するプログラム合成
２つの立体のサイズと体積の差がデータとして，10 例ほど与えられ，そこからそれらを説明できる体積差を求める式を合成します．ここでは，GP の効率的

16

はじめにな手法として「自動定義関数（ADF）」という考え方を用いています．GP フレー
ムワークは，ADF にも対応でき，コンソールアプリケーションとして実現します．
14 人工蟻を進化させる：Santa Fe trail 問題の解法
32×32 の領域に断片的に散らばっている餌をすべて集めるための行動ができる蟻を進化させる問題です．ここで用いた餌の散らばりパターンを「Santa Fetrail」と一般的に称しています．GUI として実現します．
15 倉庫番はつらいかも：倉庫内の荷物の片づけ問題
倉庫内にあるブロックを，倉庫の四隅と壁際に片づける行動を合成します．
GUI として実現します．
このような構成となっていますが，オブジェクト指向や C++ をご存知の方は第 1 部の Chapter1 〜 3 をスキップされても，他の章を読むための支障にはなりません．したがって，他の章については，興味のある章から読まれると良いでしょう．ただ，無駄な重複を避けるため，後の章では，前章への参照を指示している部分もあります．

ソースプログラムについて
本書では，全ソースプログラムをダウンロードサービスで提供しています．
プログラムの開発環境は GUI 系が C++Builder で，CUI（コンソールアプリケーション）系は Cygnus の G++ コンパイラを用いています．また，VC++ 版については本文中では説明を加えていませんが，準備してあります．各アプリケーションに対する，これら 3 種の処理系の対応状況を次の表に示します．
表において，「○」はソースとしてダウンロードファイル中に含まれていることを示しています．
なお開発した，処理系のバージョンは以下のとおりです．この後のバージョンについては確認していません．

17

はじめに処理系対応表

CUI 系部

2部章のテーマ

GUI 系VC++C++
Builder

VC++

○

○

――

○

○

○

―

――

――

○

○

遊びじゃないスケジュール

○

○

○

――

まずは多数決をとってみよう

○

○

○

―

―

この次に来る数はなんだろう

○

○

○

――

G++

C++
Builder

どの順序で作ろうか？

○

時間割は奥深い後片づけはむずかしい？！

３部 体積の差がわかるかい

○

○

○

―

―

人工蟻を進化させる―

――

○

○

倉庫番はつらいかも

―

――

○

○

G++

B2.0 (B2.01)

C++Builder

1.0，3.0

VC++

4.2，5.0

ダウンロードサービスについては、p .383「ダウンロードサービスのご利用について」もあわせてご覧ください．

18

第 1 部 オブジェクト指向とフレームワーク

第 1 部 オブジェクト指向とフレームワーク
本書では，GA と GP のプログラムをいくつか作りますが，C や Pascal といった従来の手続き型言語は使わず，オブジェクト指向言語を使うことにします．オブジェクト指向言語としては，C++，Smalltalk などが古くから知られていますが，新しい言語として Java も広まっています．本書では，処理系が豊富にあること，国際標準であること，処理速度が高速であることなどの理由により，C++ を記述言語として用います．Java も JIT を用いれば，高速になりますが，それでも C++ の 2 倍ほどの時間がかかってしまいます（時が解決してくれるでしょう）．GA も GP も計算処理を大量に行いますので処理速度は重要です．
ここでは，C++ を前提としてオブジェクト指向の継承，カプセル化，多態性，動的束縛といった性質を前もって説明しておきます．オブジェクト指向は難しいといわれていますが，これらの難しそうな言葉は，互いに密接に関連しています．また，オブジェクト指向の性質をうまく使うことで，拡張性と柔軟性と再利用性を向上させることができます．GA や GP のプロ
グラムは多くの部分を共通にすることができますから，オブジェクト指向の性質を適用しフレームワークとして構成すると，応用する問題固有の部分だけに力を集中させることができます．実際，フレームワークを利用すれば，問題固有の部分をコーディングするだけですむので，1 〜 2 日で完成させることができます．
まずは，オブジェクト指向の世界へ入ってみましょう．

190

第 2 部 遺伝的アルゴリズムの応用

第 2 部 遺伝的アルゴリズムの応用
遺伝的アルゴリズム（Genetic Algorithms：GA）は，John Holland が提唱した考え方で，Darwin の進化論をそのまま探索や最適解の求解に応用したものです．進化には遺伝子（染色体）が大きく関与しますが，GA においても遺伝子に相当する記号を決め，それの複数の並びを染色体とした配列が基本的な役割を担っています．この遺伝子の記号化を遺伝子コーディングと呼びます．GA の応用においては，解こうとする問題の何を遺伝子として表現するかがもっとも重要なポイントになります．
一般に，現実の問題には，多くの複雑な制約条件が存在しますが，遺伝子コーディングをうまく行うと，それらの制約条件のいくつかを自動的に満たすことも可能です．

268

第 3 部 遺伝的プログラミングの応用

第 3 部 遺伝的プログラミングの応用
遺伝的プログラミング（Genetic Programming：GP）は，John R. Koza が提唱した考え方で，先の GA の兄弟分にあたります．GA は制約条件下で目的関数を最大にするような解表現を求めます．GP もその意味では，同じことを行っていますが，解自体の表現を直接合成するのではなく，与えられた関数集合を使ったプログラムとして合成し，解はそのプログラムの実行結果として表現されます．したがって，その性質から，GA の解の結果は静的な表現ですが，GP は動作，振る舞い，行動など動的な表現も可能となります．また，GA では，求められた解がなぜそうなのかを説明できませんが，GP では，合成されたプログラムを解析することで，最終的な解の説明を加えることも可能です．

371

あとがき

あとがき
「はじめに」でも記しましたが，本書は，かなり欲張った内容となっています．
しかしながら，適用する問題が変わっても，GA や GP の基本構造は変わりません．その部分をオブジェクト指向フレームワークとしておけば，あとが格段に楽になります．それについては，本書の内容からおわかりいただけたかと思います．オブジェクト指向についての解説を第 1 部としたのはそのためであり，オブジェクト指向フレームワークが GA や GP を構成するための適切な構造を持っていることを示しておきたかったからです．
本書のもう 1 つの大きな目的は，GA や GP の応用事例を紹介して，読者の方々の研究や実適用の便を図ることにあります．GA については，前著で応用を含めた事例を掲載しましたが，本書ではさらに，実適用へ一歩近づけるよう工夫をしました．GP については，LISP が基本言語としてよく使われていますが，本書では C++ で実装することにより，あわよくば実適用ができるように準備をしておこうというわけです．GP の応用事例についても，簡単なものから知的な活動を目指すものまで，GP 適用の差が出るように工夫をしています．
まだまだ，探求が足りないとお叱りを受けるところもあるかとは思いますが，単なるまねではなく，可能なかぎり独自性が出るようにしています（進化には多様性が重要な役割を果たします）．特に GA においては，遺伝子型と表現型との間に横たわるギャップは，遺伝子型をどう解釈して変換すると埋められるか，言い換えると表現型に結びつけられるかについては，考え方を表現するようにつとめました．本書で示している考え方が決して，最良というわけではありませんが，何らかのヒントにはなるでしょう．
GA や GP に関する各章の内容やオブジェクト指向フレームワークについての解説が，読者諸兄の研究や仕事にいくらかでもお役にたてれば幸いです．
末筆ながら，本書の企画を快く受諾していただき，丹念な編集をしていた
だいた，パーソナルメディア社出版部の方々にお礼を申し上げます．

・・・ この続きは、製品版でお楽しみください。

購入ご案内
iPad 用 PDF リーダアプリ「Smooth Reader」をご利用の方は、以下のボタンをタップすると購入手続きに進みます。

その他の電子書籍や、全国書店でお買い求めになれる紙書籍に関する情報は、当社ウェブページをご覧ください。
→ http://www.personal-media.co.jp/book/384

著者略歴／著作権表示／奥付■著者略歴

平野廣美（ひらのひろみ）

昭和 51 年，京都大学航空工学科卒業後，( 株 ) 日本 CAD，( 株 ) 新日鉄ソリューションズ
等を経て，現在，楽天株式会社 楽天技術研究所に在籍．
大学卒業後まもなくして人工知能に興味を持ち始め，Lisp や Prolog の処理系の開発に従事する。また，日本語によるデータベースの検索システムの開発や工場等の生産計画の最適化，テキストマイニングなどの知識処理などを行ってきた．
著書に『C でつくるニューラルネットワーク』『応用事例でわかる遺伝的アルゴリズムプログラミング』『続・遺伝的アルゴリズムと遺伝的プログラミング』『C++ と Java でつくるニューラルネットワーク』（いずれも，パーソナルメディア刊）がある．

本書に関する情報を web サイトでご案内しております．

http://www.personal-media.co.jp/book/comp/173/

本書に記載されているハードウェア名，ソフトウェア名は一般に各メーカーの登録商標または商標です．

遺伝的アルゴリズムと遺伝的プログラミング
オブジェクト指向フレームワークによる構成と応用
2000 年 2 月 29 日

初版 1 刷発行（書籍版）

2011 年 6 月 15 日

iPad 版 発行

著者

平野廣美

発行所

パーソナルメディア株式会社〒 141-0031

東京都品川区西五反田 1-29-1

コイズミビルTEL（03）5759-8303 ／ FAX（03）5759-8306
E-mail pub@personal-media.co.jp
http://www.personal-media.co.jp©2000 Hiromi Hirano

385

著者略歴／著作権表示／奥付