Genetic algorithm
Please find below source code for the genetic algorithm used in the TSP Solver app. Please use as you see fit, but let me know of any improvements you make to the code and if it is used in a professional setting. The code is written in Obective C in XCode targeted for iOS applications. The class has a set of delegates which must be implemented by the calling application.
TSPGAEngine.h:
// Created by Magnus Ytterstad on 7/17/13.
// Copyright (c) 2013 Magnus Ytterstad. All rights reserved.
#import <Foundation/Foundation.h>
#import "TSPCity.h"
#import "TSPTrail.h"
@protocol TSPGASetupDelegate <NSObject>
@property (nonatomic) NSUInteger gaPoolSize;
@property (nonatomic) NSUInteger gaGenerationsPerRun;
@property (nonatomic) NSUInteger gaNumSolutions;
@property (nonatomic) NSUInteger gaNumGenerations;
@property (nonatomic)NSUInteger gaNumReproduction;
@property (nonatomic)NSUInteger gaNumCrossover;
@property (nonatomic)NSUInteger gaNumMutation;
@property (nonatomic)NSUInteger gaNumInsertMutation;
@property (nonatomic)NSUInteger gaNumMirrorMutation;
@end
@interface TSPGAEngine : NSObject
@property (nonatomic)NSUInteger poolSize;
@property (nonatomic)NSUInteger generationsPerRun;
@property (nonatomic, strong)NSArray *genes;
@property (nonatomic)BOOL isSetup;
@property (nonatomic, weak) id <TSPGASetupDelegate> delegate;
-(void) runGAOneGeneration;
- (void) setupWithCities:(NSArray *)cities startingWith: (TSPCity * )city;
-(TSPTrail *)getBestTrail;
-(NSArray *)getGenes;
@end
TSPGAEngine.c:
//
// TSPGAEngine.m
// TSP_GA2
//
// Created by Magnus Ytterstad on 7/17/13.
// Copyright (c) 2013 Magnus Ytterstad. All rights reserved.
//
#import "TSPGAEngine.h"
@interface TSPGAEngine ()
@end
#define GENE_MIN_LEN 2
@implementation TSPGAEngine
-(double)randPCT{
return ((double)arc4random()/0x1000000000);
}
- (void) runGAOneGeneration{
self.delegate.gaNumGenerations += 1;
self.poolSize = self.delegate.gaPoolSize;
self.generationsPerRun = self.delegate.gaGenerationsPerRun;
double totalDistanceInPool = 0.0;
for (id obj in self.genes){
if ([obj isKindOfClass:[TSPTrail class]]){
TSPTrail * curr = (TSPTrail *) obj;
totalDistanceInPool += curr.trailTotalDistance;
}
}
NSUInteger numberOfReproduction = self.delegate.gaNumReproduction +1;
NSUInteger numberOfCrossover = self.delegate.gaNumCrossover +1;
NSUInteger numberOfMutation = self.delegate.gaNumMutation +1;
NSUInteger numberOfMirrorMutation = self.delegate.gaNumInsertMutation;
NSUInteger numberOfInsertMutation = self.delegate.gaNumMirrorMutation;
NSUInteger numberOfMultipleMutation = 0; // need to fix bug first!
TSPTrail * tempTrail = self.genes[0];
NSUInteger geneLength = [tempTrail.theTrail count];
NSMutableArray * newGeneration = [[NSMutableArray alloc]init];
//reproduction: select x genes from the sorted pool starting with the best.
NSUInteger maxReproduction = numberOfReproduction;
if (self.poolSize<numberOfReproduction){
maxReproduction = self.poolSize;
}
for (int i = 0;i<maxReproduction;i++){
id obj = self.genes[i];
TSPTrail *curr = (TSPTrail *)obj;
//curr.creationMethod = @"Reproduction";
[newGeneration addObject:curr];
}
//crossover: Mix sequences from two randomly selected genes
for (int i = 0; i< numberOfCrossover;i++){
NSUInteger parent1Index = arc4random()%[self.genes count];
NSUInteger parent2Index = arc4random()%[self.genes count];
NSUInteger lenGeneFromParent1 = arc4random()%(geneLength/2)+GENE_MIN_LEN;
NSUInteger startPointGeneInParent1 = arc4random()%(geneLength-lenGeneFromParent1);
TSPTrail * parent1 = self.genes[parent1Index];
TSPTrail * parent2 = self.genes[parent2Index];
NSMutableArray * newGene = [[NSMutableArray alloc]initWithCapacity:geneLength];
for (NSUInteger ii = 0; ii<geneLength;ii++){ //fill array before we insert parent 1 gene with dummy for now
[newGene addObject:[NSString stringWithFormat:@"dummy"]];
}
for (NSUInteger i = startPointGeneInParent1; i<startPointGeneInParent1+ lenGeneFromParent1;i++){
[newGene replaceObjectAtIndex:i withObject: parent1.theTrail[i]];
}
NSUInteger k = 0;
for (NSUInteger j = 0;j < [parent2.theTrail count];j++){
TSPCity * parent2Node = parent2.theTrail[j];
if (![self nodeExistsInArray:newGene node: parent2Node]){
while ([newGene[k] isKindOfClass:[TSPCity class]]){
k++;
}
[newGene replaceObjectAtIndex:k withObject:parent2Node];
}
}
TSPTrail * newTrail = [[TSPTrail alloc]init];
newTrail.theTrail = newGene;
newTrail.creationMethod = @"Crossover";
newTrail.generation = self.delegate.gaNumGenerations;
newTrail.trailParent1 = parent1;
newTrail.trailParent2 = parent2;
[newTrail calcNameAndDistance];
[newGeneration addObject:newTrail];
self.delegate.gaNumSolutions += 1;
NSLog(@"New gene: start at: %d len: %d",startPointGeneInParent1,lenGeneFromParent1);
NSLog(@"Parent1: %@",parent1.cromosome);
NSLog(@"Parent2: %@",parent2.cromosome);
NSLog(@"NewGene: %@",newTrail.cromosome);
}
// Swap Mutation: select two nodes in randomly selected gene and swap places
for (int i = 0; i<numberOfMutation; i++){
NSUInteger parentIndex = arc4random()%[self.genes count];
NSUInteger node1Ind = arc4random()%(geneLength-1)+1;
NSUInteger node2Ind = arc4random()%(geneLength-1)+1;
while (node2Ind == node1Ind){
node2Ind = arc4random()%(geneLength-1)+1;
}
if (node2Ind < 1 || node1Ind < 1){
NSLog(@"0");
}
id obj = self.genes[parentIndex];
if ([obj isKindOfClass:[TSPTrail class]]){
TSPTrail * curr = (TSPTrail *)obj;
TSPCity * node1 = curr.theTrail[node1Ind];
TSPCity * node2 = curr.theTrail[node2Ind];
TSPTrail * newTrail = [[TSPTrail alloc]init];
NSMutableArray *mutArray = [curr.theTrail mutableCopy];
[mutArray replaceObjectAtIndex:node1Ind withObject:node2];
[mutArray replaceObjectAtIndex:node2Ind withObject:node1];
newTrail.theTrail = mutArray;
newTrail.creationMethod = @"SwapMutation";
newTrail.generation = self.delegate.gaNumGenerations;
newTrail.trailParent1 = curr;
[newTrail calcNameAndDistance];
[newGeneration addObject:newTrail];
self.delegate.gaNumSolutions += 1;
}
}
//Insert Mutation: select random node in random gene and move it forward
for (int i = 0; i<numberOfInsertMutation;i++){
NSUInteger parentIndex = arc4random()%[self.genes count];
NSUInteger nodeIndex = arc4random()%(geneLength-2)+2;
NSUInteger nodeInsertIndex = arc4random()%(nodeIndex-1)+1;
id obj = self.genes[parentIndex];
if ([obj isKindOfClass:[TSPTrail class]]){
TSPTrail * curr = (TSPTrail *)obj;
NSMutableArray *mutArray = [curr.theTrail mutableCopy];
TSPCity * node = curr.theTrail[nodeIndex];
[mutArray insertObject:node atIndex:nodeInsertIndex];
[mutArray removeObjectAtIndex:nodeIndex+1];
TSPTrail * newTrail = [[TSPTrail alloc]init];
newTrail.theTrail = mutArray;
newTrail.creationMethod = @"InsertMutation";
newTrail.generation = self.delegate.gaNumGenerations;
newTrail.trailParent1 = curr;
[newTrail calcNameAndDistance];
[newGeneration addObject:newTrail];
self.delegate.gaNumSolutions += 1;
}
}
//Mirror Mutation: change order of random number of nodes in random gene.
for (int i = 0; i<numberOfMirrorMutation;i++){
NSUInteger parentIndex = arc4random()%[self.genes count];
NSUInteger nodeIndex = arc4random()%(geneLength-1)+1;
NSUInteger mirrorGeneLen = arc4random()%(geneLength-nodeIndex)+1;
id obj = self.genes[parentIndex];
if ([obj isKindOfClass:[TSPTrail class]]){
TSPTrail * curr = (TSPTrail *)obj;
NSMutableArray *mutArray = [curr.theTrail mutableCopy];
NSUInteger backStepper = nodeIndex + mirrorGeneLen-1;
for (NSUInteger i = nodeIndex;i<nodeIndex+mirrorGeneLen;i++) {
TSPCity * node = curr.theTrail[i];
[mutArray replaceObjectAtIndex:backStepper withObject:node];
backStepper --;
}
TSPTrail * newTrail = [[TSPTrail alloc]init];
newTrail.theTrail = mutArray;
newTrail.creationMethod = @"MirrorMutation";
newTrail.generation = self.delegate.gaNumGenerations;
newTrail.trailParent1 = curr;
[newTrail calcNameAndDistance];
[newGeneration addObject:newTrail];
self.delegate.gaNumSolutions += 1;
}
}
// Multiple Mutation
for (int i = 0; i<numberOfMultipleMutation; i++){
NSUInteger parentIndex = arc4random()%[self.genes count];
NSUInteger mutationLen = arc4random()%((geneLength-2)/2)+1;
NSUInteger node1Ind;
NSUInteger node2Ind;
if (geneLength-3 > 2*mutationLen){
node1Ind = arc4random()%((geneLength-1)-2*mutationLen)+1;
node2Ind = arc4random()%(geneLength-node1Ind-2*mutationLen)+node1Ind+mutationLen-1;
}
else {
node1Ind = 1;
node2Ind = 1+mutationLen;
}
if (node2Ind < 1 || node1Ind < 1){
NSLog(@"0");
}
id obj = self.genes[parentIndex];
if ([obj isKindOfClass:[TSPTrail class]]){
TSPTrail * curr = (TSPTrail *)obj;
NSMutableArray *mutArray = [curr.theTrail mutableCopy];
for (int nodeCnt = 0;nodeCnt<mutationLen;nodeCnt++){
TSPCity * node1 = curr.theTrail[node1Ind+nodeCnt];
TSPCity * node2 = curr.theTrail[node2Ind+nodeCnt];
[mutArray replaceObjectAtIndex:node1Ind+nodeCnt withObject:node2];
[mutArray replaceObjectAtIndex:node2Ind+nodeCnt withObject:node1];
}
TSPTrail * newTrail = [[TSPTrail alloc]init];
newTrail.theTrail = mutArray;
newTrail.creationMethod = @"MassMutation";
newTrail.generation = self.delegate.gaNumGenerations;
[newTrail calcNameAndDistance];
[newGeneration addObject:newTrail];
self.delegate.gaNumSolutions += 1;
}
}
NSArray *noDuplicates = [[NSSet setWithArray: newGeneration] allObjects];
newGeneration = [noDuplicates mutableCopy];
[newGeneration sortUsingSelector:@selector(compareWithOther:)];
while ([newGeneration count] > self.poolSize){
[newGeneration removeLastObject];
}
self.genes = [newGeneration copy];
NSLog(@"NewGeneration done.");
}
-(BOOL)nodeExistsInArray:(NSMutableArray *)arr node:(TSPCity *) node{
for (int i = 0; i<[arr count]; i++){
id obj = arr[i];
if ([obj isKindOfClass:[TSPCity class]]){
TSPCity * curr = (TSPCity *)obj;
if (curr.cityId == node.cityId){
return YES;
}
}
}
return NO;
}
- (void) setupWithCities:(NSArray *)cities startingWith: (TSPCity * )city{
self.poolSize = self.delegate.gaPoolSize;
self.generationsPerRun = self.delegate.gaGenerationsPerRun;
NSMutableArray *buildArray = [[NSMutableArray alloc]initWithCapacity:self.poolSize];
for (int i = 0;i<self.poolSize; i++){
[buildArray addObject:[[TSPTrail alloc]initWithArray:cities startingWith:city]];
self.delegate.gaNumSolutions += 1;
}
self.isSetup = YES;
[buildArray sortUsingSelector:@selector(compareWithOther:)];
self.genes = buildArray;
}
-(TSPTrail *)getBestTrail{
return(TSPTrail *) self.genes[0];
}
-(NSArray *)getGenes{
return self.genes;
}
@end
|
