遺伝的アルゴリズム：ilex blog：So-netブログ

	ブログをはじめるログイン

遺伝的アルゴリズム　[プログラミング] [編集]

遺伝的アルゴリズムを知ったのはもう１０年以上も前になるでしょうか。アルゴリズムとかプログラムというものは、解析的というか、わかっている解法を実行するものだと思っていたものですから、遺伝的アルゴリズムやニューラルネットワーク、さらには最近はやりの強化学習のように、解法というかそのパラメータをプログラム自身が探索する、解法はブラックボックス、というアプローチが、とても斬新に思えたものでした。

遺伝的アルゴリズムは、基本的なものは実装も簡単なので、素人でもその強力さが実感できて面白いです。こちらの「エンジニアが正しく「I love you」と伝えるための遺伝的アルゴリズム(殺伐) 」というページを拝見して、興味が再燃したので、おなじ課題をCで組んでみました。ランダムな文字列から出発して、世代交代を繰り返し、「I love you」にたどり着けるか？

   
#include    <stdio.h>
#include    <stdlib.h>
#include    <string.h>
#include    <time.h>
#include    <unistd.h>

#define TARGET          "I love you"
#define MUTATE_CHANCE   0.5
#define GENE_NUM        20
#define NUM_OF_MUTATE   1
#define ASCII_MIN       32
#define ASCII_MAX       127

typedef struct {
    char    *gstr;
    int     gval;
}GENE;

GENE    gene[GENE_NUM];
int     gstr_len;
int     debug = 0;

void    init_gene( void );
int     eval( char * );
void    gene_sort( void );
int     comp( const void *, const void * );
void    cross( void );
void    mutate( float );
void    pr( void );
void    pr_usage( void );

// compare for qsort
int comp( const void *c1, const void *c2 ) {
    GENE    t1 = *(GENE *)c1;
    GENE    t2 = *(GENE *)c2;

    return t1.gval - t2.gval;
}

// init gene
void    init_gene() {
    int i, j;

    // allocate memory
    gstr_len = strlen( TARGET );
    for ( i = 0; i < GENE_NUM; i++ ) {
        gene[i].gstr = (char *)malloc( sizeof(char)*(gstr_len+1) );
        if ( gene[i].gstr == NULL ) {
            printf( "memory allocation faild.\n" );
            exit( EXIT_FAILURE );
        }
    }

    // generate string & sort
    srand( (unsigned)time( NULL ) );
    for ( i = 0; i < GENE_NUM; i++ ) {
        for ( j = 0; j < gstr_len; j++ ) {
            sprintf( &gene[i].gstr[j], "%c", rand()%(ASCII_MAX-ASCII_MIN)+ASCII_MIN );
        }
        gene[i].gstr[j+1] = '\0';
        gene[i].gval = eval( gene[i].gstr );
    }
    qsort( gene, sizeof(gene)/sizeof(gene[0]), sizeof(gene[0]), comp );
}

// mutation
void    mutate( float chance ) {
    int i, j, k;
    int pm;

    for ( i = 0; i < GENE_NUM; i++ ) {
        if ( chance*10 < rand()%10 ) {
            j = rand()%gstr_len;
            pm = rand()%2 == 0 ? 1 : -1;
            if ( gene[i].gstr[j] == ASCII_MIN) pm = 1;
            if ( gene[i].gstr[j] == ASCII_MAX) pm = -1;
            gene[i].gstr[j] += pm;
        }
    }
}

// evaluation
int eval( char *str ) {
    int     i, v;
    int     r = 0;
    char    target[] = TARGET;

    for ( i = 0; i < gstr_len; i++ ) {
        v = strncmp( target+i, str+i, 1 );
        r += v*v;
    }

    return( r );
}

// select & cross
void    cross() {
    int     i, cp;

    cp = rand()%gstr_len;
    for ( i = 0; i < gstr_len; i++ ) {
        if ( i < cp ) {
            gene[GENE_NUM-2].gstr[i] = gene[0].gstr[i];
            gene[GENE_NUM-1].gstr[i] = gene[1].gstr[i];
        } else {
            gene[GENE_NUM-2].gstr[i] = gene[1].gstr[i];
            gene[GENE_NUM-1].gstr[i] = gene[0].gstr[i];
        }
    }
}

// print
void    pr() {
    int i;

    for ( i = 0; i < GENE_NUM; i++ ) {
        printf( " >%2d %10s %d\n", i, gene[i].gstr, gene[i].gval );
    }
}

// usage
void    pr_usage() {
    printf( "usage: ga [-dh]\n" );
}

// main
int main( int argc, char **argv ) {
    int i, j;
    int generation = 0;
    int opt;

    // optrion
    while ( ( opt = getopt( argc, argv, "dh" ) ) != -1 ) {
        switch ( opt ) {
            case 'd':   debug = 1; break;
            case '?':
            case 'h':
            default:    pr_usage(); exit( EXIT_SUCCESS );
        }
    }

    // init
    init_gene();
    if ( debug ) pr();

    // loop
    while ( gene[0].gval > 0 ) {
        // select & cross
        cross();

        // mutation
        mutate( MUTATE_CHANCE );

        // evaluation
        for ( i = 0; i < GENE_NUM; i++ ) {
            gene[i].gval = eval( gene[i].gstr );
        }

        // sort
        qsort( gene, sizeof(gene)/sizeof(gene[0]), sizeof(gene[0]), comp );

        printf( "%4d %5d %10s\n", generation, gene[0].gval, gene[0].gstr );
        if ( debug ) pr();
        generation++;
    }
}