New libgenetic. Genetic algorithms, only good.

15 files changed, 379 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..254da6c
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,4 @@
+.*.swp
+*.o
+/.build_cache
+/libgenetic.a
diff --git a/default.bld b/default.bld
new file mode 100644
index 0000000..c5312cd
--- /dev/null
+++ b/default.bld
@@ -0,0 +1,20 @@
+target "libgenetic.a"
+{
+        rule "lib";
+        input files("src/*.cpp");
+
+        CXXFLAGS += "-I. -ggdb";
+}
+
+for src in files("src/tests/*.cpp") do
+{
+        target src.replace("src/","").replace(".cpp","")
+        {
+                rule "exe";
+                input src;
+                requires "libgenetic.a";
+
+                CXXFLAGS += "-I. -ggdb";
+                LDFLAGS += "-L. -lgenetic -lbu++ -ggdb";
+        }
+}
diff --git a/genetic b/genetic
new file mode 120000
index 0000000..e831038
--- /dev/null
+++ b/genetic
@@ -0,0 +1 @@
+src
\ No newline at end of file
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 <bu/list.h>
+
+namespace Genetic
+{
+        class Phenotype;
+        typedef Bu::List<Phenotype *> 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 <bu/random.h>
+#include <bu/sio.h>
+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 <bu/string.h>
+
+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 &copyFrom( 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 <bu/random.h>
+#include <bu/sio.h>
+
+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<const Genetic::PhenotypeBinary &>(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 &copyFrom( 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 <bu/sio.h>
+#include <bu/random.h>
+#include <bu/randomcmwc.h>
+#include <time.h>
+
+using namespace Bu;
+
+int main( int argc, char *argv[] )
+{
+        Bu::Random::setGenerator<Bu::RandomCmwc>();
+        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;
+}
+
diff --git a/tests/.gitignore b/tests/.gitignore
new file mode 100644
index 0000000..120f485
--- /dev/null
+++ b/tests/.gitignore
@@ -0,0 +1,2 @@
+*
+!/.gitignore