TSP/genetic.h at main · ahmedcali84/TSP · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#ifndef GENETIC_H
#define GENETIC_H

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

#define LENGTH 8 /* Number of Cities */
#define SIZE   10 /* Population Size */
#define MUTATION_RATE 1.0f /* Mutation Rate */
#define MAX_GENERATIONS (SIZE / 2) /* Maximum Generations */
#define STAGNATION_LIMIT 3

#define INITIAL_CAPACITY SIZE /* INITIAL CAPACITY FOR THE POPULATION */

typedef enum {
    INITIALIZE,
    SELECT_PARENTS,
    CROSSOVER,
    MUTATION,
    REPLACE,
    TERMINATE,
} States;

typedef struct City {
    float x;
    float y;
} City;

typedef struct Genome {
    unsigned int *path;  /* tracking city order array */
    unsigned int length; /* num cities */
    float fitness;
} Genome;

typedef struct Genomes {
    Genome *items;
    unsigned int count;
    unsigned int capacity;
} Genomes;

typedef struct Permutation {
    unsigned int **array;
    unsigned int count;
} Permutation;

extern City cities[LENGTH]; // city array

void swap(void *a, void *b, size_t size);
unsigned int factorial(unsigned int n);

void generate_permutations(unsigned int *a, unsigned int size, unsigned int **result, unsigned int *index, unsigned int length);
Permutation *generate_permutations_of_indices(unsigned int *indices, unsigned int length);
void print_permutations(Permutation *permutations);
void free_permutations(Permutation *permutations);

unsigned int *deep_copy_array(const unsigned int *source, const unsigned int length);
unsigned int *select_random_permutation_of_unique_indices(unsigned int length);
void print_indices(unsigned int *array, unsigned int length);

float random_float();
City generate_random_city();
float euclidean_distance(City a, City b);
void initialize_cities(unsigned int length);

float calculate_fitness(Genome *g);
Genome generate_random_genome(unsigned int length);
Genome deep_copy_genome(const Genome *source);
void mutate_genome(Genome *g, float mutation_rate);
void print_genome(FILE *stream, const Genome *g, const char *title);
void free_genome(Genome *g);

void initialize_population(Genomes *population, unsigned int size, unsigned int length);
Genomes *select_parents(const Genomes *gs);
Genome crossover(const Genomes *parents);
void append_to_population(Genomes *population, Genome *member);
void pop_from_population(Genomes *population, Genome *member);
Genome *find_weakest(Genomes *population);
Genome *find_best(Genomes *population);
void replace_worst(Genomes *population, Genome *new_member);
void print_population(FILE *stream, const Genomes *gs, const char *title);

#define PRINT_POPULATION(stream, population) print_population(stream, population, #population) /*Special Print Function*/

void free_population(Genomes *gs);

#endif  /*GENETIC_H*/