数字は独身に限る

進化計算班最終発表
竪山＆新里班
数字は独身に限る
略して・・・
要求仕様書
宮里＆与儀班から提案された「９」×「９」マスの数独の問題を
作成するプログラムを作成する。
・問題の作成には必ずGAを用いる。
・あらかじめ用意した解答に,決まった数の空白をかぶせて評価をする。
・プログラム言語は問わない。
成果物の仕様書
・問題の作成にはGAを用いた。
・あらかじめ用意した解答に,決まった数の空白をかぶせて評価をした。
・プログラム言語はC言語を用いた。
・空白数、交叉回数、個体数の変更がdokusu.hで変更可能。
・最終的な結果（問題）をresulut.txtに出力。
・マス、行、列の順に見ていき、各候補を消していくことで空白マスを
埋めていく。３種類の探索で空白マスが埋まらない場合は仮置をして
再び３種類の探索を行う。
GA設計
１.コーディング
空白の位置を構造体で定義した配列に格納し,任意の数作成する。(40個)dokusu.h の
#define BLK で指定する数字を変えることで空白の数を変更できる。
２.適応度計算
問題を読み込み,数独のルールに従い空白を埋めていく,その際の手数をカウントし評価と
する。また,仮置も１度ごとにカウントしていく。
３.選択
作成された問題にランキングをつけ,評価の高い問題を残していく。（ランキング選択）
４.交叉
選択され,ランク付けのされた上位同士交叉をし、個体を生成する。dokusu.hの
#define CHANGE の指定数を変えることで交叉回数変更可能。
５.突然変異
空白を新たに作り、作られた空白位置とは異なる位置の空白を答えに置き換え,空白の数
は固定する。
実験結果
パラメータの値
N
40//!問題生成数
BLK
40
//!空白生成数
CROPROB
MUPROB
CHANGE
MURAND
60 //! 交叉を行う確率
10 //! 突然変異が起こる確率
3600 //!世代交代数
20 //!突然変異時における格マスが変化する確率
実行方法
% make
% ./dokusu > data.txt
適応度推移図
手
数
作成された問題
感想
ところで皆さんは,この講義が始まったときに,富間先生からお借りした
参考書を返却しましたか？
私は、まだなので、今度返したいとお申します。
適応度計算に利用していた、ネットから拝借したプログラムにバグが
あり、結局プログラムを書き直さないといけないと気づいた時には軽く
絶望しました。

Download Report