第3章　遺伝的MBRを実現する

リスト3.1: グローバル変数定義

#!/bin/bash

# set -eux

# POPULATION_SIZEは、
# - 2で2回割っても余りが出ない
# - 5で1回割っても余りが出ない
# を共に満たす値であること
# すなわち、20の倍数
POPULATION_SIZE=20
GENE_LEN=446
MBR_TESTER=./mbr_tester
WORK_DIR=$(date '+%Y%m%d%H%M%S')

# ・・・以降、関数定義が続く・・・

リスト3.2: コマンドライン引数チェック

if [ $# -ge 1 ]; then
        WORK_DIR=$1
        echo "Use WORK_DIR=${WORK_DIR}"
else
        echo "Initialization"
        initialization
fi

if [ $# -ge 2 ]; then
        age=$2
        echo "It will start in the generation $age."
else
        age=0
fi

リスト3.3: メイン処理

touch enable_ge
while [ -f enable_ge ]; do
        echo "GE: age=$age"
        echo '-------------------------------------------'

        evaluation
        feedback
        mv ${WORK_DIR}/{now,$age}
        mv ${WORK_DIR}/{next,now}
        mkdir ${WORK_DIR}/next
        age=$((age + 1))

        echo
        echo
done

リスト3.4: ある時点の作業ディレクトリの状態

20180912144115/
├─ 0/
│  ├─ ch_0.dat
│  ├─ ch_1.dat
│  ├─ ch_2.dat
│  ├─ ...
│  └─ evaluation_value_list.csv
├─ 1/
│  ├─ ch_0.dat
│  ├─ ch_1.dat
│  ├─ ch_2.dat
│  ├─ ...
│  └─ evaluation_value_list.csv
├─ now/
│  ├─ ch_0.dat
│  ├─ ch_1.dat
│  ├─ ch_2.dat
│  ├─ ...
│  └─ evaluation_value_list.csv
└─ next/

リスト3.5: スクリプト終了処理

echo '-------------------------------------------'
echo "Stopped at $(date '+%Y-%m-%d %H:%M:%S')"
echo 'Continue Command'
echo "$0 ${WORK_DIR} $age"
echo '-------------------------------------------'

リスト3.6: 終了処理の出力例

-------------------------------------------
Stopped at 2018-09-14 15:17:15
Continue Command
./ge_mbr.sh 20180912144115 821
-------------------------------------------

リスト3.7: 初期個体群生成

initialization() {
        local i

        echo 'initialization'
        echo '-------------------------------------------'

        echo "WORK_DIR=${WORK_DIR}"
        mkdir -p ${WORK_DIR}/{now,next}
        for i in $(seq 0 $((POPULATION_SIZE - 1))); do
                echo "${WORK_DIR}/now/ch_$i.dat"
                generate "${WORK_DIR}/now/ch_$i.dat"
        done

        echo
        echo
}

リスト3.8: 各個体の生成

generate() {
        local file

        file=$1
        dd if=/dev/urandom of=$file bs=1 count=$GENE_LEN
        cat mbr_partition_tbl_boot_sig.dat >> $file
}

リスト3.9: 評価

evaluation() {
        local i
        local ch

        echo 'evaluation'
        echo '-------------------------------------------'

        rm -f tmp.csv

        for i in $(seq 0 $((POPULATION_SIZE - 1))); do
                echo "i=$i"
                ch=${WORK_DIR}/now/ch_$i.dat
                echo ">>>>> $ch"

                cp $ch floppy.img
                cp $ch hdd.img
                $MBR_TESTER
                exit_code=$?
                case $exit_code in
                0)
                        evaluation_value=100
                        echo "$ch has reached the answer!"
                        rm -f enable_ge
                        ;;
                1)
                        evaluation_value=1
                        echo "$ch is an ordinary child."
                        ;;
                *)
                        evaluation_value=0
                        echo "$ch is dead."
                        ;;
                esac

                echo "ch_$i.dat,${evaluation_value}" >> tmp.csv
                echo "evaluation_value=${evaluation_value}"

                echo
                echo
        done

        # 第2列で降順にソート
        sort -n -r -k 2 -t ',' tmp.csv > ${WORK_DIR}/now/evaluation_value_list.csv

        rm -f floppy.img hdd.img tmp.csv

        echo
        echo
}

リスト3.10: フィードバック(定数定義)

feedback() {
        local i

        echo 'feedback'
        echo '-------------------------------------------'

        candidates_num=$((POPULATION_SIZE / 2))
        mutation_num=$((POPULATION_SIZE / 5))
        top_num=$((POPULATION_SIZE - (candidates_num + mutation_num)))

リスト3.11: フィードバック(淘汰)

        # 淘汰
        # evaluation_value=0の個体を一番良い個体で置き換える
        echo ">>>>>>> To be culled"
        top_ch=$(awk -F',' '{print $1;exit}'    \
                ${WORK_DIR}/now/evaluation_value_list.csv)
        echo "top_ch:${WORK_DIR}/now/${top_ch}"
        for i in $(awk -F',' '$2==0{print $1}'  \
                ${WORK_DIR}/now/evaluation_value_list.csv); do
                mkdir -p ${WORK_DIR}/${age}_culled
                mv ${WORK_DIR}/now/${i} ${WORK_DIR}/${age}_culled/
                echo "save $i to ${WORK_DIR}/${age}_culled/"
                cp ${WORK_DIR}/now/${top_ch} ${WORK_DIR}/now/$i
                echo "replace ${WORK_DIR}/now/$i with ${WORK_DIR}/now/${top_ch}"
        done

        echo

リスト3.12: フィードバック(上位30%を引継ぐ)

        # (個体数 - (残した子孫の数 + 突然変異数))分の個体を、上位から順にnextへコピー
        echo ">>>>>>> Copy Top ${top_num}"
        for i in $(seq ${top_num}); do
                line=$(sed -n ${i}p ${WORK_DIR}/now/evaluation_value_list.csv)
                echo "line:$line"
                cp ${WORK_DIR}/{now,next}/$(echo $line | cut -d',' -f1)
                echo "save_to_next:${WORK_DIR}/now/$(echo $line | cut -d',' -f1)"
        done

        echo

リスト3.13: フィードバック(交叉)

        # 上位50%の個体を候補に、同数の個体をnextへ追加
        # (一様交叉を使用)
        echo '>>>>>>> Crossover'
        max_cross_times=$((candidates_num / 2))
        for cross_times in $(seq 0 $((max_cross_times - 1))); do
                echo "cross_times=${cross_times}"

                chA_idx=$(((RANDOM % candidates_num) + 1))
                chB_idx=${chA_idx}
                while [ ${chB_idx} -eq ${chA_idx} ]; do
                        chB_idx=$(((RANDOM % candidates_num) + 1))
                done
                echo "chA_idx=${chA_idx} , chB_idx=${chB_idx}"

                chA=${WORK_DIR}/now/$(sed -n ${chA_idx}p                \
                        ${WORK_DIR}/now/evaluation_value_list.csv       \
                        | cut -d',' -f1)
                chB=${WORK_DIR}/now/$(sed -n ${chB_idx}p                \
                        ${WORK_DIR}/now/evaluation_value_list.csv       \
                        | cut -d',' -f1)
                echo "chA=$chA"
                echo "chB=$chB"
                partial_crossover $chA $chB             \
                        child$((2 * cross_times)).dat   \
                        child$(((2 * cross_times) + 1)).dat

                echo
        done

        cross_idx=0
        for i in $(seq 0 $((POPULATION_SIZE - 1))); do
                [ ${cross_idx} -ge ${candidates_num} ] && break
                if [ ! -f ${WORK_DIR}/next/ch_$i.dat ]; then
                        mv child${cross_idx}.dat ${WORK_DIR}/next/ch_$i.dat
                        echo "mv child${cross_idx}.dat ${WORK_DIR}/next/ch_$i.dat"
                        cross_idx=$((cross_idx + 1))
                fi
        done

        echo

リスト3.14: フィードバック(突然変異)

        # 個体数の20%を突然変異させ、nextへ追加
        echo '>>>>>>> Mutation'
        for i in $(seq 0 $((POPULATION_SIZE - 1))); do
                if [ ! -f ${WORK_DIR}/next/ch_$i.dat ]; then
                        generate ${WORK_DIR}/next/ch_$i.dat
                        echo "mutated:${WORK_DIR}/next/ch_$i.dat"
                fi
        done

        echo
        echo
}

リスト3.15: ASCII表示可能文字を出力するかテスト

static uint8 test_ch(uint8 ch)
{
        if ((0x21 <= ch) && (ch <= 0x7e)) {
                printf("ch=%c(0x%02x)\n", ch, ch);
                return 1;
        } else
                return 0;
}