Mercurial > projects > aid
changeset 0:4b2e8e8a633e
Repository setup.
| author | revcompgeek |
|---|---|
| date | Mon, 03 Mar 2008 19:28:10 -0700 |
| parents | |
| children | 5dd9f598bcd8 |
| files | branches/.hidden downloads/.hidden tags/.hidden trunk/aid/astar.d trunk/aid/containers/heap.d trunk/aid/ga.d trunk/aid/maze/generate.d trunk/bcd/sys/times.cc trunk/bcd/sys/times.d trunk/dsss.conf trunk/ga_code.d trunk/ga_maze.d trunk/mazegen.d trunk/test.py |
| diffstat | 11 files changed, 1178 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/aid/astar.d Mon Mar 03 19:28:10 2008 -0700 @@ -0,0 +1,42 @@ +/*+++++++++++++++++++++++++++++++++++++++++++ + + A* algorithm + + + By Matt Peterson + + +++++++++++++++++++++++++++++++++++++++++++*/ + +module aid.astar; + +import mintl.arrayheap; + +class Node(DATA) { + int xloc; + int yloc; + int fitness; + private int fitg; + Node* parent = null; + DATA data; + + this(DATA d, int g){ + data = d; + fitness = g; + fitg = g; + } + this(DATA d, int g, Node* p){ + data = d; + parent = p; + if(parent) fitness = parent.fitness + g; + fitg = g; + } + int opCmp(Node other){ + return this.fitness - other.fitness; + } +} + +class AStar(DATA) { + alias Node!(DATA) Node; + alias DATA[] delegate(DATA) getChildren; + ArrayHeap!(Node) openList; + ArrayHeap!(Node) closedList; + DATA[] run(DATA start){ + + } +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/aid/containers/heap.d Mon Mar 03 19:28:10 2008 -0700 @@ -0,0 +1,282 @@ +/*++++++++++++++++++++++++++++++++++++++++++++ + + Heap sorted array + + + By Matt Peterson + + ++++++++++++++++++++++++++++++++++++++++++++*/ + +/*class Heap(Value) { + Value[] array; + int tail; + public int capacity(){ + // This returns the current capacity of the heap. + return array.length; + } + public int size(){ + // This returns the number of items in the heap. + return tail; + } + + void capacity(int c){ + // This sets the capacity to c. + if(c < tail) c = tail; + array.length = c; + } + void insert(Value v){ + // Inserts a value and sorts it to it's correct position. + if(tail >= size()) capacity(size()+10); + array[++tail] = v; + int i = tail; + while(i > 0 && array[i/2] > array[i]){ + array[i] = array[i/2]; + array[i/2] = v; + i /= 2; + } + } + Value removeHead(){ + Value ret = array[0]; + array[0] = array[tail]; + tail--; + i = 0; + while( + } + +}*/ + +struct Heap(Value, Alloc = GCAllocator) { + + alias ArrayHeap ContainerType; + alias Value ValueType; + alias size_t IndexType; + + Value[] data; ///< backing array. null by default, grows as needed + + invariant { + assert( tail <= data.length ); + } + + /** signature for a custom comparison function */ + alias int delegate(Value* a, Value* b) CompareFcn; + + /** Set custom comparison function. */ + void compareFcn(CompareFcn cmp) { + cmpFcn = cmp; + } + + /** Get heap contents as dynamic array slice of backing array. */ + Value[] values() { + return data[0..tail]; + } + + /** Adds an item to the heap. Increases capacity if needed. */ + void addTail(Value v) { + capacity(tail+1); + data[tail++] = v; + fixupTail(); + } + + /** Removes and returns the head item of the heap. If the target + * heap is empty an IndexOutOfBoundsException is thrown unless + * version=MinTLNoIndexChecking is set. + */ + Value takeHead() { + version (MinTLNoIndexChecking) { + // no error checking + } else { + if (tail == 0) + throw new IndexOutOfBoundsException(); + } + Value val = data[0]; + data[0] = data[--tail]; + data[tail] = Value.init; + fixupHead(); + return val; + } + + /** Removes the head item of the heap. */ + void removeHead() { + version (MinTLNoIndexChecking) { + // no error checking + } else { + if (tail == 0) + throw new IndexOutOfBoundsException(); + } + data[0] = data[--tail]; + data[tail] = Value.init; + fixupHead(); + } + + /** Get the length of heap. */ + size_t length() { + return tail; + } + + /** Test if container is empty. */ + bool isEmpty() { + return tail == 0; + } + + /** Clear all contents. */ + void clear() { + static if (is(Alloc == GCAllocator)) { + } else { + if (data.ptr) + Alloc.gcFree(data.ptr); + } + *this = ArrayHeap.init; + } + + /** Get the nth item in the heap from head. */ + Value opIndex(size_t n) { + return data[n]; + } + + /** Get a pointer to the nth item in the heap */ + Value* lookup(size_t n) { + return &data[n]; + } + + /** Set the nth item in the heap. */ + void opIndexAssign(Value val, size_t n) { + data[n] = val; + } + + /** Duplicates a heap. */ + ArrayHeap dup() { + ArrayHeap res; + static if (is(Alloc == GCAllocator)) { + res.data = data.dup; + } else { + Value* p = cast(Value*)Alloc.malloc(data.length * Value.sizeof); + res.data = p[0 .. data.length]; + res.data[] = data[]; + } + res.tail = tail; + res.cmpFcn = cmpFcn; + return res; + } + + /** Test for equality of two heaps. */ + int opEquals(ArrayHeap c) { + size_t len = length; + if (len !is c.length) + return 0; + size_t a,b; + a = 0; + b = 0; + TypeInfo ti = typeid(Value); + for (size_t k = 0; k < len; k++) { + if (!ti.equals(&data[a],&c.data[b])) + return 0; + a++; + b++; + } + return 1; + } + + /** Compare two heaps. */ + int opCmp(ArrayHeap c) { + size_t len = length; + if (len > c.length) + len = c.length; + size_t a,b; + a = 0; + b = 0; + TypeInfo ti = typeid(Value); + for (size_t k = 0; k < len; k++) { + int cmp = ti.compare(&data[a],&c.data[b]); + if (cmp) + return cmp; + a++; + b++; + } + return cast(int)length - cast(int)c.length; + } + + /** Returns a short string representation of the heap. */ + char[] toString() { + return "[ArrayHeap length " ~ std.string.toString(tail) ~ "]"; + } + + /** Iterates over the heap from head to tail calling delegate to + * perform an action. The value is passed to the delegate. + */ + int opApplyNoKey(int delegate(inout Value x) dg){ + int res = 0; + for (size_t k=0; k < tail; k++) { + res = dg(data[k]); + if (res) break; + } + return res; + } + + /** Iterates over the heap from head to tail calling delegate to + * perform an action. The index from 0 and the value are passed + * to the delegate. + */ + int opApplyWithKey(int delegate(inout size_t n, inout Value x) dg){ + int res = 0; + for (size_t k=0; k < tail; k++) { + res = dg(k,data[k]); + if (res) break; + } + return res; + } + + alias opApplyNoKey opApply; + alias opApplyWithKey opApply; + + /** Ensure the minimum capacity of heap. */ + void capacity(size_t cap) { + if (cap > data.length) { + cap = (cap+1)*2; + static if (is(Alloc == GCAllocator)) { + data.length = cap; + } else { + Value* p = data.ptr; + p = cast(Value*)Alloc.gcRealloc(p,cap*Value.sizeof); + p[data.length .. cap] = Value.init; + data = p[0 .. cap]; + } + } + } + + // Helper functions + + // enforce heap invariant after a new head + private void fixupHead() { + size_t n = 0; + TypeInfo ti = typeid(Value); + if (cmpFcn is null) { + cmpFcn = cast(CompareFcn)&ti.compare; + } + for (;;) { + size_t n1 = 2*n+1; + if (n1 >= tail) break; + if ((n1 != tail-1) && (cmpFcn(&data[n1],&data[n1+1]) < 0)) + n1++; + if (cmpFcn(&data[n],&data[n1]) < 0) { + ti.swap(&data[n],&data[n1]); + n = n1; + } else { + break; + } + } + } + + // enforce heap invariant after a new tail + private void fixupTail() { + size_t n = tail-1; + TypeInfo ti = typeid(Value); + if (cmpFcn is null) { + cmpFcn = cast(CompareFcn)&ti.compare; + } + size_t n1 = (n-1)>>1; + while ((n > 0) && (cmpFcn(&data[n],&data[n1]) > 0)) { + ti.swap(&data[n],&data[n1]); + n = n1; + n1 = (n-1)>>1; + } + } + + private CompareFcn cmpFcn; + private size_t tail; +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/aid/ga.d Mon Mar 03 19:28:10 2008 -0700 @@ -0,0 +1,226 @@ +/*********************************** + * Provides a set of classes * + * for using Genetic Algorithms. * + * * + * Author: Matt P. * + * Version: 0.1 * + ***********************************/ + +module aid.ga; + +import tango.math.Random; +import tango.io.Stdout; + +void removeIndex(Gene[] array, uint index){ + //scope(failure) Stdout.format("E: removeIndex {}", index).newline; + if (index == 0) + array = array[1..$]; + else if (index == array.length) + array = array[0..$-1]; + else + array = array[0..index-1] ~ array[index+1..$]; +} + +class Gene { + char[] geneSequence; + private double fit = -1; // Save the fitness value so that it doesn't have to be calculated more than once. + private GeneticAlgorithm* ga; + + this(GeneticAlgorithm* a){ + ga = a; + } + + this(Gene g, GeneticAlgorithm* a){ + scope(failure) Stdout("E: Gene clone").newline; + geneSequence = g.geneSequence.dup; + this(a); + } + + double fitness(){ // Get property + if (fit == -1){ + fit = ga.calculateFitness(geneSequence); + } + return fit; + } + + Gene[] crossover(Gene other){ + Gene gene1 = new Gene(this,ga),gene2 = new Gene(other,ga); + auto r = Random.shared; + auto len = geneSequence.length; + char[] temp; + + //scope(failure) Stdout.format("E: crossover {}").newline; + + if (ga.crossoverType == 2){ + //Stdout("1").flush; + uint point1 = r.next(len-2)+1; + uint point2 = r.next(len-2)+1; + while (point1 == point2) + point2 = r.next(len); + if (point2 < point1){ + scope uint t = point1; + point1 = point2; + point2 = t; + } + //Stdout("2").newline; + scope(failure) Stdout.format("Ed: {},{}",point1,point2).newline; + //Stdout(point1)(", ")(point2).newline; + temp = gene1.geneSequence[point1..point2].dup; + //Stdout("4").flush; + gene1.geneSequence[point1..point2] = gene2.geneSequence[point1..point2].dup; + //Stdout("5").flush; + gene2.geneSequence[point1..point2] = temp; + //Stdout("6").flush; + } else if (ga.crossoverType == 1) { + uint point = r.next(len-2)+1; + temp = gene1.geneSequence[point..$].dup; + gene1.geneSequence[point..$] = gene2.geneSequence[point..$]; + gene2.geneSequence[point..$] = temp; + } else { // Uniform crossover + for (int i = 0; i < len / 2; i++){ + uint point = r.next(len); + + auto t = gene1.geneSequence[point]; + gene1.geneSequence[point] = gene2.geneSequence[point]; + gene2.geneSequence[point] = t; + } + } + return [gene1,gene2]; + } + + Gene mutate(){ + Gene g = new Gene(this,ga); + uint i = Random.shared.next(g.geneSequence.length); + g.geneSequence[i] = ga.getRandomChar(i); + return g; + } +} + +class Generation { + private Gene[] genes; + private uint population; + private GeneticAlgorithm* ga; + + public this(GeneticAlgorithm* g, bool generate = false){ + ga = g; + population = ga.startPopulation; + if (generate) generateGenes(); + } + + public this(Generation gen){ + genes = gen.genes; + ga = gen.ga; + } + + public Generation evolve(){ + Generation newGen = new Generation(ga); + + // Use tournament selection to create a new Generation + uint livingPop = cast(uint)(population * ga.survivalRate); + newGen.population = population; + newGen.genes.length = population; + for (auto i = 0; i < livingPop; i++){ + uint t = tournamentSelect(); + newGen.genes[i] = genes[t]; + //genes.removeIndex(t); + } + + // Cross over the left over genes + for (auto i = livingPop; i < population; i+=2){ + uint i1 = tournamentSelect(), i2 = tournamentSelect(); + while (i1 == i2) + i2 = tournamentSelect(); + Gene g1 = genes[i1], g2 = genes[i2]; + + Gene[] gs = g1.crossover(g2); + + newGen.genes[i..i+2] = gs[]; + if (ga.deleteOnCrossover){ + genes.removeIndex(i1); + genes.removeIndex(i2); + } + } + + // Mutate a small amount of genes + for (auto i = 0; i < population * ga.mutationRate; i++){ + uint index = Random.shared.next(newGen.genes.length); + newGen.genes[index] = newGen.genes[index].mutate(); + } + + return newGen; + } + + private void generateGenes(){ + scope(failure) Stdout("E: generateGenes").newline; + genes.length = population; + for (uint i = 0; i < population; i++){ + Gene t = new Gene(ga); + t.geneSequence = ga.getRandomGenotype(); + genes[i] = t; + } + } + + private uint tournamentSelect(){ + Gene[4] gens; + uint[4] indices; + scope(failure) Stdout("E: tournamentSelect").newline; + for (uint i = 0; i < 4; i++){ + indices[i] = Random.shared.next(genes.length); + gens[i] = genes[indices[i]]; + } + double max = gens[0].fitness; + uint index = indices[0]; + foreach (i,g; gens){ + if (g.fitness > max){ + max = g.fitness; + index = indices[i]; + } + } + return index; + } +} + +class GeneticAlgorithm { + public double delegate(char[]) calculateFitness; // Set these before you do anything with the library + public char[] delegate() getRandomGenotype; + public char delegate(uint index) getRandomChar; + public double survivalRate = 0.5; + public double mutationRate = 0.05; + public bool deleteOnCrossover = true; + public int crossoverType = 1; // 1 point crossover + public uint startPopulation = 1000; + public bool verbose = false; + public uint bailout = 1000; + + public double fitnessThreshold; + + public uint run(){ + //Stdout("t").flush; + Generation currGen = new Generation(&this,true); + //Stdout("test").flush; + bool stop = false; + uint generation = 1; + double average; + double max; + while (true){ + if (verbose) max = 0; + if (verbose) average = 0; + foreach (Gene g; currGen.genes){ + if (verbose) average += g.fitness; + + if (verbose) if (g.fitness > max) max = g.fitness; + if (g.fitness >= fitnessThreshold){ + stop = true; + } + } + if (verbose) average /= currGen.genes.length; + if (verbose) Stdout.formatln("Gen: {} Avg: {:.4} Max: {:.4}",generation, average, max); + if (stop || generation >= bailout) return generation; + currGen = currGen.evolve(); + generation++; + } + } +} + + +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/aid/maze/generate.d Mon Mar 03 19:28:10 2008 -0700 @@ -0,0 +1,18 @@ +module ai.maze.generate; + +import tango.math.Random; + +class MazeGenerator { +public: + MazeCell[][] generate(uint w, uint h){ + Random r = Random.shared; + MazeCell[][] maze = new MazeCell[w][h]; + uint x = r.next(w); + uint y = r.next(h); + + } +} + +struct MazeCell { + bool n=true,w=true,s=true,e=true,visited=false; +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/bcd/sys/times.cc Mon Mar 03 19:28:10 2008 -0700 @@ -0,0 +1,67 @@ +/* THIS FILE GENERATED BY bcd.gen */ +#include <stdlib.h> +#include <string.h> +#include "../bind.h" +#include "times.h" +extern "C" { +void _BCD_delete_3tms( *This) { +delete This; +} +typedef long unsigned int _BCD__67___darwin_clock_t; +typedef _BCD__67___darwin_clock_t _BCD__6_clock_t; +typedef * _BCD__8___darwin_ucontext64_t; +typedef * _BCD__10___darwin_ucontext_t; +typedef * _BCD__12___darwin_stack_t; +typedef unsigned char _BCD_array__13[16]; +typedef _BCD_array__13 _BCD__14___darwin_uuid_t; +typedef unsigned int _BCD__83___uint32_t; +typedef _BCD__83___uint32_t _BCD__16___darwin_useconds_t; +typedef _BCD__83___uint32_t _BCD__17___darwin_uid_t; +typedef int _BCD__84___int32_t; +typedef _BCD__84___int32_t _BCD__19___darwin_suseconds_t; +typedef _BCD__83___uint32_t _BCD__20___darwin_sigset_t; +typedef * _BCD__22___darwin_pthread_t; +typedef * _BCD__24___darwin_pthread_rwlockattr_t; +typedef * _BCD__26___darwin_pthread_rwlock_t; +typedef * _BCD__28___darwin_pthread_once_t; +typedef * _BCD__30___darwin_pthread_mutexattr_t; +typedef * _BCD__32___darwin_pthread_mutex_t; +typedef long unsigned int _BCD__33___darwin_pthread_key_t; +typedef * _BCD__35___darwin_pthread_condattr_t; +typedef * _BCD__37___darwin_pthread_cond_t; +typedef * _BCD__39___darwin_pthread_attr_t; +typedef _BCD__84___int32_t _BCD__40___darwin_pid_t; +typedef long long int _BCD__82___int64_t; +typedef _BCD__82___int64_t _BCD__42___darwin_off_t; +typedef short unsigned int _BCD__85___uint16_t; +typedef _BCD__85___uint16_t _BCD__44___darwin_mode_t; +typedef * _BCD__46___darwin_mcontext64_t; +typedef * _BCD__48___darwin_mcontext_t; +typedef unsigned int _BCD__78___darwin_natural_t; +typedef _BCD__78___darwin_natural_t _BCD__50___darwin_mach_port_name_t; +typedef _BCD__50___darwin_mach_port_name_t _BCD__49___darwin_mach_port_t; +typedef _BCD__83___uint32_t _BCD__51___darwin_ino_t; +typedef _BCD__83___uint32_t _BCD__52___darwin_id_t; +typedef _BCD__83___uint32_t _BCD__53___darwin_gid_t; +typedef unsigned int _BCD__54___darwin_fsfilcnt_t; +typedef unsigned int _BCD__55___darwin_fsblkcnt_t; +typedef _BCD__84___int32_t _BCD__56___darwin_dev_t; +typedef _BCD__84___int32_t _BCD__57___darwin_blksize_t; +typedef _BCD__82___int64_t _BCD__58___darwin_blkcnt_t; +typedef long int _BCD__64___darwin_time_t; +typedef long int _BCD__65___darwin_ssize_t; +typedef _BCD__83___uint32_t _BCD__66___darwin_socklen_t; +typedef int _BCD__68___darwin_wint_t; +typedef int _BCD__70___darwin_wchar_t; +typedef _BCD__70___darwin_wchar_t _BCD__69___darwin_rune_t; +typedef char * _BCD__72___darwin_va_list; +typedef long unsigned int _BCD__73___darwin_size_t; +typedef int _BCD__74___darwin_ptrdiff_t; +typedef union _BCD__76___darwin_mbstate_t; +typedef int _BCD__77___darwin_ct_rune_t; +typedef long int _BCD__79___darwin_intptr_t; +typedef long long unsigned int _BCD__81___uint64_t; +typedef short int _BCD__87___int16_t; +typedef unsigned char _BCD__89___uint8_t; +typedef signed char _BCD__91___int8_t; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/bcd/sys/times.d Mon Mar 03 19:28:10 2008 -0700 @@ -0,0 +1,17 @@ +/* THIS FILE GENERATED BY bcd.gen */ +module bcd.sys.times; +align(4): +//public import bcd.sys._types; +alias uint clock_t; +extern (C) uint times(tms *); +struct tms { +uint tms_utime; +uint tms_stime; +uint tms_cutime; +uint tms_cstime; +} +long iutime(){ + tms t; + times(&t); + return t.tms_utime; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/dsss.conf Mon Mar 03 19:28:10 2008 -0700 @@ -0,0 +1,5 @@ +[aid] +exclude=aid/maze/ +[ga_code.d] +[ga_maze.d] +[mazegen.d]
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/ga_code.d Mon Mar 03 19:28:10 2008 -0700 @@ -0,0 +1,2 @@ +/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + Genetic Algorithm Code Test + + Author: Matt P. + + Version: 0.5 + + + + Runs a genetic algorithm test using a simple code + + guessing algorithm. + + + + Usage: ga_code [options] + + Options: + + -h + + Prints this information. + + -v + + Turns on verbose output. + + -m float + + Specifies the mutation rate for each generation. + + Default: 0.05 + + + + -d float + + Specifies the survival rate for each generation. + + Default: 0.5 + + + + -p integer + + Specifies the population for each generation. + + Default: 1000 + + + + -l integer + + Specifies how long the code to be guessed is. + + Default: 20 + + + + -n integer + + Specifies how many possibilities there are for + + each character of the code string. + + Default: 20 + + + + -r integer + + Specifies the number of times to repeat the test. + + Default: 20 + + + + -c char + + Specifies the crossover type + + s / 1 - One point crossover + + t / 2 - Two point crossover + + u / 3 - Uniform crossover + + Default: s + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/ module ga_code; import aid.ga; import tango.math.Random; import tango.math.Math; import tango.io.Stdout; //import tango.text.String; import Float = tango.text.convert.Float; import Integer = tango.text.convert.Integer; import bcd.sys.times; char[] target; int numChars = 20; int stringLen = 20; double average(double[] array){ double avg = 0; foreach (double v; array) avg += v; avg /= array.length; return avg; } double stdDev(double[] array){ double avg = average(array); double stddev = 0; foreach (double v; array){ stddev += (v - avg) * (v - avg); } stddev = sqrt(stddev/array.length); return stddev; } class Foo { public double calculateFitness(char[] gene){ double fitness=0; for (uint i = 0; i < stringLen; i++){ if (gene[i] == target[i]) fitness += 1; } return fitness; } public char[] getRandomGenotype(){ char[] t; t.length = stringLen; for (int i = 0; i < stringLen; i++){ t[i] = Random.shared.next(numChars) + 'a'; } return t; } public char getRandomChar(uint index){ return cast(char)(Random.shared.next(numChars)+'a'); } } void usage(){ auto s = "Usage: ga_test [options] \n" "Options: \n" "-h \n" " Prints this information. \n" "-v \n" " Turns on verbose output. \n" "-m float \n" " Specifies the mutation rate for each generation. \n" " Default: 0.05 \n" " \n" "-d float \n" " Specifies the survival rate for each generation. \n" " Default: 0.5 \n" " \n" "-p integer \n" " Specifies the population for each generation. \n" " Default: 1000 \n" " \n" "-l integer \n" " Specifies how long the code to be guessed is. \n" " Default: 20 \n" " \n" "-n integer \n" " Specifies how many possibilities there are for \n" " each character of the code string. \n" " Default: 20 \n" " \n" "-r integer \n" " Specifies the number of times to repeat the test.\n" " Default: 20 \n" " \n" "-c char \n" " Specifies the crossover type \n" " s / 1 - One point crossover \n" " t / 2 - Two point crossover \n" " u / 3 - Uniform crossover \n" " Default: s "; Stdout(s).newline; } void main(char[][] args){ Foo f = new Foo(); GeneticAlgorithm ga = new GeneticAlgorithm(); ga.calculateFitness = &f.calculateFitness; ga.getRandomGenotype = &f.getRandomGenotype; ga.getRandomChar = &f.getRandomChar; ga.fitnessThreshold = stringLen; int rep = 20; bool dotime=true; for (auto i = 1; i < args.length; i++){ char[] arg = args[i]; switch (arg){ case "-h": usage(); return; case "-m": ga.mutationRate = Float.parse(args[++i]); break; case "-d": ga.survivalRate = Float.parse(args[++i]); break; case "-p": ga.startPopulation = Integer.parse(args[++i]); break; case "-l": stringLen = Integer.parse(args[++i]); ga.fitnessThreshold = stringLen; break; case "-n": numChars = Integer.parse(args[++i]); break; case "-r": rep = Integer.parse(args[++i]); break; case "-v": ga.verbose = true; break; case "-c": auto t = args[++i]; switch (t){ case "s","1": ga.crossoverType = 1; break; case "t","2": ga.crossoverType = 2; break; default: ga.crossoverType = 3; } break; case "-b": ga.bailout = Integer.parse(args[++i]); break; case "-t": dotime = false; break; default: Stdout.format("Unknown parameter: {}",arg).newline; usage(); return; } } + target = ga.getRandomGenotype(); double[] time; double[] gens; long start,end; for(auto i = 0; i < rep; i++){ if(dotime) start = iutime(); uint generations = ga.run(); if(dotime) end = iutime() - start; if(dotime) time ~= end; gens ~= generations; } if(dotime) Stdout.format("{0}, {1:.5}, {2}, {3:.5}", average(gens),stdDev(gens),average(time),stdDev(time)).newline; else Stdout.format("{0}, {1:.5}", average(gens),stdDev(gens)).newline; //", {2}, {3:.5}" ,average(time),stdDev(time) } \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/ga_maze.d Mon Mar 03 19:28:10 2008 -0700 @@ -0,0 +1,331 @@ +/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + + Genetic Algorithm Maze Test + + + Author: Matt P. + + + Version: 0.5 + + + + + + Runs a genetic algorithm test using a maze generation + + + and guessing algorithm. + + + + + + Usage: ga_maze [options] + + + Options: + + + -h + + + Prints this information. + + + -v + + + Turns on verbose output. + + + -m float + + + Specifies the mutation rate for each generation. + + + Default: 0.05 + + + + + + -d float + + + Specifies the survival rate for each generation. + + + Default: 0.5 + + + + + + -p integer + + + Specifies the population for each generation. + + + Default: 1000 + + + + + + -l integer + + + Specifies the maximum length of the solution code.+ + + Default: 20 + + + + + + -r integer + + + Specifies the number of times to repeat the test. + + + Default: 20 + + + + + + -c char + + + Specifies the crossover type + + + s / 1 - One point crossover + + + t / 2 - Two point crossover + + + u / 3 - Uniform crossover + + + Default: s + + + + + + -s integer integer + + + Specifies the size of the maze + + + Default: 7 7 + + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/ + + +module ga_maze; + +import aid.ga; +import tango.math.Random; +import tango.math.Math; +import tango.io.Stdout; +//import tango.text.String; +import Float = tango.text.convert.Float; +import Integer = tango.text.convert.Integer; + +import bcd.sys.times; + +char[] chars = "NESW"; + +//int numChars = 20; +int stringLen = 28; + +bool[][] maze; +int w = 7; +int h = 7; + +double average(double[] array){ + double avg = 0; + foreach (double v; array) + avg += v; + avg /= array.length; + return avg; +} + +double stdDev(double[] array){ + double avg = average(array); + double stddev = 0; + foreach (double v; array){ + stddev += (v - avg) * (v - avg); + } + stddev = sqrt(stddev/array.length); + return stddev; +} + +bool[][] generateMaze(uint width, uint height){ + bool[][] maze; + + maze.length = width; + + for (auto i = 0; i < width; i++){ + maze[i].length = height; + } + + bool rowStart = true; + bool vertical; + for (auto i = 1; i < width; i+=2){ + vertical = rowStart; + rowStart = !rowStart; + + for (auto j = 1; j < height; j+=2){ + maze[i][j] = true; + if (vertical) + maze[i + ((Random.shared.next(2)-1)?-1:1)][j] = true; + else + maze[i][j + ((Random.shared.next(2)-1)?-1:1)] = true; + vertical = !vertical; + } + } + + return maze; +} + +void printMaze(bool[][] m, bool[][] trail = null,char e = '.', char f = 'X', bool outline = true){ + if (outline){ + Stdout("+"); + for (auto j = 0; j < m[0].length; j++){ + Stdout("-"); + } + Stdout("+").newline; + } + + for (auto i = 0; i < m.length; i++){ + if (outline) Stdout("|"); + for (auto j = 0; j < m[i].length; j++){ + if(m[i][j]) Stdout(""~f); + else if(trail && trail[i][j]) Stdout("+"); + else Stdout(""~e); + } + if (outline) Stdout("|").newline; + } + if (outline){ + Stdout("+"); + for (auto j = 0; j < m[0].length; j++){ + Stdout("-"); + } + Stdout("+").newline; + } +} + +/++++++++++++++++++++++++++ Foo ++++++++++++++++++++++++++++++/ + +class Foo { + int count = 0; + public double calculateFitness(char[] gene){ + + bool canMove(int x, int y){ + return ((x >= 0) && (x < w) && (y >= 0) && (y < h) && (!maze[x][y])); + } + + double square(int v){ + return v*v; + } + + /*bool[][] trail; + + trail.length = w; + for(uint i = 0; i < w; i++){ + trail[i].length = h; + }*/ + + double fitness=0; + int x = 0; + int y = 0; + for (uint i = 0; i < gene.length; i++){ + //trail[x][y] = true; + //Stdout(""~gene[i]); + if(gene[i] == 'N' && canMove(x,y-1)) y--; + if(gene[i] == 'E' && canMove(x+1,y)) x++; + if(gene[i] == 'S' && canMove(x,y+1)) y++; + if(gene[i] == 'W' && canMove(x-1,y)) x--; + + if (x == w-1 && y == h-1){ + return 100; + } + } + + fitness = 100 - sqrt(square(x-(w-1)) + square(y-(h-1))); + /*if(count < 20){ + Stdout.format("{} {:.4}",gene,fitness).newline; + //printMaze(maze,trail); + count++; + }*/ + return fitness; + } + + public char[] getRandomGenotype(){ + char[] t; + t.length = stringLen; + for (int i = 0; i < stringLen; i++){ + t[i] = chars[Random.shared.next(chars.length)]; + } + return t; + } + + public char getRandomChar(uint index){ + return chars[Random.shared.next(chars.length)]; + } +} + +/++++++++++++++++++++++ End Foo ++++++++++++++++++++++++++++++/ + +void usage(){ + auto s = + "Usage: ga_maze [options] \n" + "Options: \n" + "-h \n" + " Prints this information. \n" + "-v \n" + " Turns on verbose output. \n" + "-m float \n" + " Specifies the mutation rate for each generation. \n" + " Default: 0.05 \n" + " \n" + "-d float \n" + " Specifies the survival rate for each generation. \n" + " Default: 0.5 \n" + " \n" + "-p integer \n" + " Specifies the population for each generation. \n" + " Default: 1000 \n" + " \n" + "-l integer \n" + " Specifies the maximum length of the solution code.\n" + " Default: 20 \n" + " \n" + "-n integer \n" + " Specifies how many possibilities there are for \n" + " each character of the code string. \n" + " Default: 20 \n" + " \n" + "-r integer \n" + " Specifies the number of times to repeat the test. \n" + " Default: 20 \n" + " \n" + "-c char \n" + " Specifies the crossover type \n" + " s / 1 - One point crossover \n" + " t / 2 - Two point crossover \n" + " u / 3 - Uniform crossover \n" + " Default: s "; + Stdout(s).newline; +} + +void main(char[][] args){ + Foo f = new Foo(); + GeneticAlgorithm ga = new GeneticAlgorithm(); + ga.calculateFitness = &f.calculateFitness; + ga.getRandomGenotype = &f.getRandomGenotype; + ga.getRandomChar = &f.getRandomChar; + ga.fitnessThreshold = 100; + int rep = 20; + bool dotime = true; + + + for (auto i = 1; i < args.length; i++){ + char[] arg = args[i]; + switch (arg){ + case "-h": + usage(); + return; + case "-m": + ga.mutationRate = Float.parse(args[++i]); + break; + case "-d": + ga.survivalRate = Float.parse(args[++i]); + break; + case "-p": + ga.startPopulation = Integer.parse(args[++i]); + break; + case "-l": + stringLen = Integer.parse(args[++i]); + //ga.fitnessThreshold = stringLen; + break; + case "-r": + rep = Integer.parse(args[++i]); + break; + case "-v": + ga.verbose = true; + break; + case "-s": + w = Integer.parse(args[++i]); + h = Integer.parse(args[++i]); + stringLen = 2*(w+h); + break; + case "-c": + auto t = args[++i]; + switch (t){ + case "s","1": + ga.crossoverType = 1; + break; + case "t","2": + ga.crossoverType = 2; + break; + default: + ga.crossoverType = 3; + } + break; + case "-b": + ga.bailout = Integer.parse(args[++i]); + break; + case "-t": + dotime = false; + break; + default: + Stdout.format("Unknown parameter: {}",arg).newline; + usage(); + return; + } + } + + double[] time; + double[] gens; + long start,end; + double generations; + + for(auto i = 0; i < rep; i++){ + maze=generateMaze(w,h); + + if(dotime) start = iutime(); + generations = ga.run(); + if(dotime) end = iutime() - start; + + if(dotime) time ~= end; + gens ~= generations; + } + + if(dotime) Stdout.format("{0}, {1:.5}, {2}, {3:.5}", average(gens),stdDev(gens),average(time),stdDev(time)).newline; + else Stdout.format("{0}, {1:.5}", average(gens),stdDev(gens)).newline; //", {2}, {3:.5}" ,average(time),stdDev(time) +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/mazegen.d Mon Mar 03 19:28:10 2008 -0700 @@ -0,0 +1,128 @@ +/++++++++++++++++++++++++++++++++++++++++++++++++ + + Maze Generation + + + Author: Matt P. + + + Version: 1.0 + + + + + + Generates a simple maze with odd dimensions. + + ++++++++++++++++++++++++++++++++++++++++++++++++/ + +module mazegen; + +import tango.math.Random; +import tango.io.Stdout; +import Integer = tango.text.convert.Integer; + +void usage(){ + Stdout( +"Usage: mazegen width height [options]\n" +"Width and height must be odd and greater than or equal to 5.\n" +"Options:\n" +" -e char\n" +" Set the empty block character to char.\n" +" -f char\n" +" Set the filled block character to char.\n" +" -b\n" +" Disables printing of the border.\n" +" -i\n" +" Prints out how many possible mazes there are for that size and quit.\n").flush; +} + +bool[][] generateMaze(uint width, uint height){ + bool[][] maze; + + maze.length = width; + + for (auto i = 0; i < width; i++){ + maze[i].length = height; + } + + bool rowStart = true; + bool vertical; + for (auto i = 1; i < width; i+=2){ + vertical = rowStart; + rowStart = !rowStart; + + for (auto j = 1; j < height; j+=2){ + maze[i][j] = true; + if (vertical) + maze[i + ((Random.shared.next(2)-1)?-1:1)][j] = true; + else + maze[i][j + ((Random.shared.next(2)-1)?-1:1)] = true; + vertical = !vertical; + } + } + + return maze; +} +void printMaze(bool[][] m,char e = ' ', char f = 'X', bool outline = true){ + if (outline){ + Stdout("+"); + for (auto j = 0; j < m[0].length; j++){ + Stdout("-"); + } + Stdout("+").newline; + } + + for (auto i = 0; i < m.length; i++){ + if (outline) Stdout("|"); + for (auto j = 0; j < m[i].length; j++){ + if(m[i][j]) Stdout(""~f).flush; + else Stdout(""~e).flush; + } + if (outline) Stdout("|").newline; + } + if (outline){ + Stdout("+"); + for (auto j = 0; j < m[0].length; j++){ + Stdout("-"); + } + Stdout("+").newline; + } +} + +void main(char[][] args){ + char empty = ' '; + char filled = 'X'; + + if(args.length < 3){ + usage(); + return; + } + + uint width = Integer.parse(args[1]); + uint height = Integer.parse(args[2]); + bool frame = true; + + if (width % 2 != 1 || height % 2 != 1 || width < 5 || height < 5){ + usage(); + return; + } + + for (auto i = 3; i < args.length; i++){ + char[] arg = args[i]; + switch (arg){ + case "-h": + usage(); + return; + case "-e": + empty = args[++i][0]; + break; + case "-f": + filled = args[++i][0]; + break; + case "-i": + Stdout("There are 2^")( (( width - 1 ) / 2 ) * (( height - 1 ) / 2 ) )(" different maze types for that size.").newline; + return; + case "-b": + frame = false; + default: + Stdout.format("Unknown parameter: {}",arg).newline; + usage(); + return; + } + } + + bool[][] maze = generateMaze(width,height); + + printMaze(maze,empty,filled,frame); +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/trunk/test.py Mon Mar 03 19:28:10 2008 -0700 @@ -0,0 +1,60 @@ +#!/usr/bin/python + +from subprocess import * + +def frange(*args): + l = len(args) + if l == 1: # only to + f = 0 + t = args[0] + step = 1 + elif l == 2: # from, to + start, stop = args + step = 1 + elif l == 3: + start, stop, step = args + k = (stop-start)/step+1 + return map(lambda x, f=start, s=step: f+s*x, range(max(0, int(k)))) + +prefix = "/Users/matthew/Desktop/D/ai/" +output_prefix = "/Users/matthew/Desktop/D/ai/tests/" + +print "Running..." + + +repetitions=100 + +tests = [ + ["ga_code","mutation-rate", "-m",frange(0.0,0.05,0.01) + frange(0.1,1,0.05),[]], + ["ga_code","population", "-p",frange(500,5000,500),[]], + ["ga_code","survival-rate", "-d",frange(0.2,0.8,0.05),[]], + ["ga_code","crossover-type","-c",frange(1,3,1),[]], + ["ga_code","code-length", "-l",frange(10,30,1),[]], + + ["ga_maze","mutation-rate","-m",frange(0.0,0.05,0.01) + frange(0.1,1,0.05),[]], + ["ga_maze","population", "-p",frange(500,5000,500),["-s","9","9"]], + ["ga_maze","survival-rate", "-d",frange(0.2,0.8,0.05),[]], + ["ga_maze","crossover-type","-c",frange(1,3,1),[]], + ["ga_maze","code-length", "-l",frange(10,30,1),[]] +] + +def runTest(exe,name,switch,vrange,addparams): + f = open(output_prefix + ("%s_%s_generations.csv" % (exe,name)),"w") + f2 = open(output_prefix + ("%s_%s_times.csv" % (exe,name)),"w") + + for i in vrange: + print i + p = Popen([prefix + exe,switch,str(i),"-r",str(repetitions),"-b","100"]+addparams,stdout=PIPE,bufsize=-1) + p.wait() + r = "".join(p.stdout.readlines()) + r = r.split(","); + f.write("%s,%s,%s\n" % (str(i),r[0],r[1])) + f2.write("%s,%s,%s" % (str(i),r[2],r[3])) + f.close() + f2.close() +#try: +for test in tests: + print "%s: %s" % (test[0],test[1]) + runTest(test[0],test[1],test[2],test[3],test[4]) +#except: +# print "Stopped" \ No newline at end of file