From 40ee7ad5aeadeb9823e1cd6e1218a1999c608a65 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Mon, 9 Jul 2012 08:39:37 -0600 Subject: New libgenetic. Genetic algorithms, only good. --- src/operator.cpp | 10 +++++ src/operator.h | 25 ++++++++++++ src/operatorbasic.cpp | 48 +++++++++++++++++++++++ src/operatorbasic.h | 32 +++++++++++++++ src/phenotype.cpp | 10 +++++ src/phenotype.h | 36 +++++++++++++++++ src/phenotypebinary.cpp | 101 ++++++++++++++++++++++++++++++++++++++++++++++++ src/phenotypebinary.h | 29 ++++++++++++++ src/population.cpp | 10 +++++ src/population.h | 14 +++++++ src/tests/binary.cpp | 37 ++++++++++++++++++ 11 files changed, 352 insertions(+) create mode 100644 src/operator.cpp create mode 100644 src/operator.h create mode 100644 src/operatorbasic.cpp create mode 100644 src/operatorbasic.h create mode 100644 src/phenotype.cpp create mode 100644 src/phenotype.h create mode 100644 src/phenotypebinary.cpp create mode 100644 src/phenotypebinary.h create mode 100644 src/population.cpp create mode 100644 src/population.h create mode 100644 src/tests/binary.cpp (limited to 'src') diff --git a/src/operator.cpp b/src/operator.cpp new file mode 100644 index 0000000..7324856 --- /dev/null +++ b/src/operator.cpp @@ -0,0 +1,10 @@ +#include "genetic/operator.h" + +Genetic::Operator::Operator() +{ +} + +Genetic::Operator::~Operator() +{ +} + diff --git a/src/operator.h b/src/operator.h new file mode 100644 index 0000000..8688667 --- /dev/null +++ b/src/operator.h @@ -0,0 +1,25 @@ +#ifndef GENETIC_OPERATOR_H +#define GENETIC_OPERATOR_H + +#include + +namespace Genetic +{ + class Phenotype; + typedef Bu::List PhenotypeList; + + class Operator + { + public: + Operator(); + virtual ~Operator(); + + virtual Phenotype *random()=0; + virtual int parentCount()=0; + virtual Phenotype *mate( const PhenotypeList &lParents )=0; + + private: + }; +}; + +#endif diff --git a/src/operatorbasic.cpp b/src/operatorbasic.cpp new file mode 100644 index 0000000..ce37f78 --- /dev/null +++ b/src/operatorbasic.cpp @@ -0,0 +1,48 @@ +#include "genetic/operatorbasic.h" +#include "genetic/phenotype.h" + +#include +#include +using namespace Bu; + +Genetic::OperatorBasic::OperatorBasic( Phenotype *pProgenitor, + float fMutationRate ) : + pProgenitor( pProgenitor ), + fMutationRate( fMutationRate ) +{ +} + +Genetic::OperatorBasic::~OperatorBasic() +{ + delete pProgenitor; +} + +Genetic::Phenotype *Genetic::OperatorBasic::random() +{ + Genetic::Phenotype *pNew = pProgenitor->makeEmptyOffspring(); + pNew->randomize(); + return pNew; +} + +Genetic::Phenotype *Genetic::OperatorBasic::mate( + const Genetic::PhenotypeList &lParents ) +{ + Genetic::Phenotype *pChild = lParents.first()->makeEmptyOffspring(); + + // Right now, we assume both parents have the same amount of "DNA" + int iSplitPoint = ((uint32_t)Bu::Random::rand())%lParents.first()->getSize(); + pChild->copyFrom( *lParents.first(), 0, iSplitPoint ); + pChild->copyFrom( *lParents.last(), iSplitPoint, + lParents.last()->getSize()-iSplitPoint ); + + // Mutate the child some + for( int j = 0; j < pChild->getSize(); j++ ) + { + //sio << Bu::Random::randNorm() << sio.nl; + if( Bu::Random::randNorm() <= fMutationRate ) + pChild->mutate( j, 1.0 ); + } + + return pChild; +} + diff --git a/src/operatorbasic.h b/src/operatorbasic.h new file mode 100644 index 0000000..2eaf198 --- /dev/null +++ b/src/operatorbasic.h @@ -0,0 +1,32 @@ +#ifndef GENETIC_OPERATOR_BASIC_H +#define GENETIC_OPERATOR_BASIC_H + +#include "genetic/operator.h" + +namespace Genetic +{ + /** + * Very simple genetic operator that covers all the basics. It will do + * single cut Phenotype splicing between two parents, and random mutation + * on the child. All work is based on a progenitor Phenotype, which is the + * template for creating new, random Phenotypes. OperatorBasic takes + * ownership of the progenitor and will delete it when OperatorBasic is + * destroyed. + */ + class OperatorBasic : public Operator + { + public: + OperatorBasic( Phenotype *pProgenitor, float fMutationRate ); + virtual ~OperatorBasic(); + + virtual Phenotype *random(); + virtual int parentCount() { return 2; } + virtual Phenotype *mate( const PhenotypeList &lParents ); + + private: + Phenotype *pProgenitor; + float fMutationRate; + }; +}; + +#endif diff --git a/src/phenotype.cpp b/src/phenotype.cpp new file mode 100644 index 0000000..1eca170 --- /dev/null +++ b/src/phenotype.cpp @@ -0,0 +1,10 @@ +#include "genetic/phenotype.h" + +Genetic::Phenotype::Phenotype() +{ +} + +Genetic::Phenotype::~Phenotype() +{ +} + diff --git a/src/phenotype.h b/src/phenotype.h new file mode 100644 index 0000000..7c564d5 --- /dev/null +++ b/src/phenotype.h @@ -0,0 +1,36 @@ +#ifndef GENETIC_PHENOTYPE_H +#define GENETIC_PHENOTYPE_H + +#include + +namespace Genetic +{ + class Phenotype + { + public: + Phenotype(); + virtual ~Phenotype(); + + virtual int getSize()=0; + virtual Phenotype &randomize()=0; + /** + * Modify the given location by the given magnitude. The magnitude + * should be between -1.0 and 1.0 inclusive. A 0.0 indicates no + * change. + */ + virtual void mutate( int iLocation, float fMagnitude )=0; + virtual Phenotype ©From( const Phenotype &rSrc, int iStart, + int iSize, int iDest=-1 )=0; + /** + * Produces a Phenotype class that can be used to contain the data for + * an offspring. The produced phenotype will be compatible, but empty. + */ + virtual Phenotype *makeEmptyOffspring( int iNewSize=-1 )=0; + + virtual Bu::String toString()=0; + + private: + }; +}; + +#endif diff --git a/src/phenotypebinary.cpp b/src/phenotypebinary.cpp new file mode 100644 index 0000000..d16588b --- /dev/null +++ b/src/phenotypebinary.cpp @@ -0,0 +1,101 @@ +#include "genetic/phenotypebinary.h" + +#include +#include + +using namespace Bu; + +// Bits per word +#define BPW (sizeof(uint_fast32_t)*8) +#define wordsForBits( x ) (((x)/BPW)+(((x)%BPW)?1:0)) +#define wordWithBit( x ) ((x)/BPW) + +Genetic::PhenotypeBinary::PhenotypeBinary( int iSize, bool bRandom ) : + iSize( iSize ), + iWords( wordsForBits(iSize) ), + aGenes( NULL ) +{ + aGenes = new uint_fast32_t[iWords]; + if( bRandom ) + randomize(); +} + +Genetic::PhenotypeBinary::~PhenotypeBinary() +{ + delete[] aGenes; +} + +Genetic::Phenotype &Genetic::PhenotypeBinary::randomize() +{ + for( int j = 0; j < iWords*sizeof(uint_fast32_t); j++ ) + { + ((uint8_t *)aGenes)[j] = (uint8_t)Bu::Random::rand(); + } + + return *this; +} + +void Genetic::PhenotypeBinary::mutate( int iLocation, float fMagnitude ) +{ + if( fMagnitude > -0.5 && fMagnitude < 0.5 ) + return; + + aGenes[wordWithBit(iLocation)] = + (aGenes[wordWithBit(iLocation)]&(~(1<<((iLocation)%BPW)))) | + ((~aGenes[wordWithBit(iLocation)])&((1<<((iLocation)%BPW)))); +} + +Genetic::Phenotype *Genetic::PhenotypeBinary::makeEmptyOffspring( + int iNewSize ) +{ + if( iNewSize < 0 ) + iNewSize = iSize; + + return new PhenotypeBinary( iSize ); +} + +Genetic::Phenotype &Genetic::PhenotypeBinary::copyFrom( const Phenotype &rSrc, + int iStart, int iCount, int iDest ) +{ + const PhenotypeBinary &rbSrc = + dynamic_cast(rSrc); + if( iDest < 0 ) + iDest = iStart; + + // Fist draft, very sloppy: bit by bit copy, this is stupid, but easy + for( int j = 0; j < iCount; j++ ) + { + int wd = wordWithBit(j+iDest); + int ws = wordWithBit(j+iStart); + if( (rbSrc.aGenes[ws]&(1<<((j+iStart)%BPW))) == 0) + { + aGenes[wd] &= ~(1<<((j+iDest)%BPW)); + } + else + { + aGenes[wd] |= (1<<((j+iDest)%BPW)); + } + } + + /* + iStart%BPW + int iWords = wordsForBits(iCount); + for( int j = wordWithBit(iStart); j < iWords; j++ ) + { + } + */ + + return *this; +} + +Bu::String Genetic::PhenotypeBinary::toString() +{ + Bu::String sRet; + for( int j = 0; j < iSize; j++ ) + { + sRet += (aGenes[j/BPW]&(1<<(j%BPW)))?'1':'0'; + } + + return sRet; +} + diff --git a/src/phenotypebinary.h b/src/phenotypebinary.h new file mode 100644 index 0000000..72435ed --- /dev/null +++ b/src/phenotypebinary.h @@ -0,0 +1,29 @@ +#ifndef GENETIC_PHENOTYPE_BINARY_H +#define GENETIC_PHENOTYPE_BINARY_H + +#include "genetic/phenotype.h" + +namespace Genetic +{ + class PhenotypeBinary : public Phenotype + { + public: + PhenotypeBinary( int iSize, bool bRandom=false ); + virtual ~PhenotypeBinary(); + + virtual int getSize() { return iSize; } + virtual Phenotype &randomize(); + virtual void mutate( int iLocation, float fMagnitude ); + virtual Phenotype *makeEmptyOffspring( int iNewSize=-1 ); + virtual Phenotype ©From( const Phenotype &rSrc, int iStart, + int iCount, int iDest=-1 ); + virtual Bu::String toString(); + + private: + int iSize; + int iWords; + uint_fast32_t *aGenes; + }; +}; + +#endif diff --git a/src/population.cpp b/src/population.cpp new file mode 100644 index 0000000..85b859e --- /dev/null +++ b/src/population.cpp @@ -0,0 +1,10 @@ +#include "genetic/population.h" + +Genetic::Population::Population() +{ +} + +Genetic::Population::~Population() +{ +} + diff --git a/src/population.h b/src/population.h new file mode 100644 index 0000000..0fdad32 --- /dev/null +++ b/src/population.h @@ -0,0 +1,14 @@ +#ifndef GENETIC_POPULATION_H +#define GENETIC_POPULATION_H + +namespace Genetic +{ + class Population + { + public: + Population(); + virtual ~Population(); + }; +}; + +#endif diff --git a/src/tests/binary.cpp b/src/tests/binary.cpp new file mode 100644 index 0000000..717c171 --- /dev/null +++ b/src/tests/binary.cpp @@ -0,0 +1,37 @@ +#include "genetic/phenotypebinary.h" +#include "genetic/operatorbasic.h" + +#include +#include +#include +#include + +using namespace Bu; + +int main( int argc, char *argv[] ) +{ + Bu::Random::setGenerator(); + Bu::Random::seed( time( NULL ) ); + + Genetic::OperatorBasic op( new Genetic::PhenotypeBinary( 45 ), 0.1 ); + Genetic::Phenotype *pPb1 = op.random(); + Genetic::Phenotype *pPb2 = op.random(); + Genetic::Phenotype *pPb3; + + sio << pPb1->toString() << sio.nl; + sio << pPb2->toString() << sio.nl; + + Genetic::PhenotypeList lParents; + lParents.append( pPb1 ); + lParents.append( pPb2 ); + pPb3 = op.mate( lParents ); + + sio << pPb3->toString() << sio.nl; + + delete pPb1; + delete pPb2; + delete pPb3; + + return 0; +} + -- cgit v1.2.3