genetic-algorithm.zig

const std = @import("std");
const math = std.math;
const rand = std.rand;
const time = std.time;

// const POPULATION_SIZE = 10;
// const MAX_NUMBER_OF_GENERATIONS = 1500;

const MAX_NUMBER_OF_GENERATIONS = 100000;
const POPULATION_SIZE = 1000;
const MUTATION_PROBABILITY = 30;
const MUTATION_PERCENTAGE = 5;
const MUTATION_PRECISION = 100;
const NATURAL_SELECTION = 2;
const BEST_FITNESS = math.floatMax(f64);
const WORST_FITNESS = math.floatMin(f64);

const Solution = struct {
    x: f64,
    y: f64,
    z: f64,
    fitness: f64 = WORST_FITNESS,

    fn init(x: f64, y: f64, z: f64) Solution {
        var solution = Solution{ .x = x, .y = y, .z = z };
        solution.fitness = fitness(solution);
        return solution;
    }

    fn toString(solution: Solution) []u8 {
        std.debug.print("( x={}, y={}, z={}, fitness={} )", .{ solution.x, solution.y, solution.z, solution.fitness });
        return "";
    }
};

const RankedSolution = struct { solution: Solution, fitness: f64 };
const Generation = [POPULATION_SIZE]Solution;

fn printGeneration(generation: Generation) void {
    for (generation) |solution| {
        std.debug.print("{s}\n", .{solution.toString()});
    }
}

fn sortSolutionsInReverseOrder(comptime _: type, a: Solution, b: Solution) bool {
    return a.fitness > b.fitness;
}

fn heuristic(input: Solution) f64 {
    const x = input.x;
    const y = input.y;
    const z = input.z;

    return 6 * math.pow(f64, x, 3) + 9 * math.pow(f64, y, 2) + 90 * z - 25;
}

fn fitness(solution: Solution) f64 {
    const ans = heuristic(solution);

    if (ans == 0) {
        return BEST_FITNESS;
    } else {
        return math.pow(f64, ans, -1);
    }
}

fn mutate(generation: Generation, random: *const rand.Random) Generation {
    const parents = generation[0..NATURAL_SELECTION];
    var nextGeneration: Generation = undefined;
    var i: u64 = 0;

    while (i < POPULATION_SIZE) : (i += 1) {
        const randomIndex = random.intRangeLessThan(u64, 0, parents.len);
        const chosenParent = parents[randomIndex];
        var x: f64 = 0;
        var y: f64 = 0;
        var z: f64 = 0;

        const mutationFactorX = random.intRangeLessThan(i64, -1 * MUTATION_PERCENTAGE * MUTATION_PRECISION, MUTATION_PERCENTAGE * MUTATION_PRECISION);
        const mutationPercentageX = @intToFloat(f64, mutationFactorX) / (MUTATION_PRECISION * 100); // times 100 to convert it to percentage
        const mutationProbabilityX = random.intRangeLessThan(u64, 0, 101);

        if (mutationProbabilityX <= MUTATION_PROBABILITY) {
            x = chosenParent.x + chosenParent.x * mutationPercentageX;
        } else {
            x = chosenParent.x;
        }

        const mutationFactorY = random.intRangeLessThan(i64, -1 * MUTATION_PERCENTAGE * MUTATION_PRECISION, MUTATION_PERCENTAGE * MUTATION_PRECISION);
        const mutationPercentageY = @intToFloat(f64, mutationFactorY) / (MUTATION_PRECISION * 100); // times 100 to convert it to percentage
        const mutationProbabilityY = random.intRangeLessThan(u64, 0, 101);
        if (mutationProbabilityY <= MUTATION_PROBABILITY) {
            y = chosenParent.y + chosenParent.y * mutationPercentageY;
        } else {
            y = chosenParent.y;
        }

        const mutationFactorZ = random.intRangeLessThan(i64, -1 * MUTATION_PERCENTAGE * MUTATION_PRECISION, MUTATION_PERCENTAGE * MUTATION_PRECISION);
        const mutationPercentageZ = @intToFloat(f64, mutationFactorZ) / (MUTATION_PRECISION * 100); // times 100 to convert it to percentage
        const mutationProbabilityZ = random.intRangeLessThan(u64, 0, 101);
        if (mutationProbabilityZ <= MUTATION_PROBABILITY) {
            z = chosenParent.z + chosenParent.z * mutationPercentageZ;
        } else {
            z = chosenParent.z;
        }

        nextGeneration[i] = Solution.init(x, y, z);
    }
    return nextGeneration;
}

pub fn main() void {
    var generator = rand.DefaultPrng.init(@intCast(u64, time.milliTimestamp()));
    const random = generator.random();
    var solutions: Generation = undefined;
    for (solutions) |_, i| {
        const x = @intToFloat(f64, random.intRangeLessThan(u64, 0, 10000));
        const y = @intToFloat(f64, random.intRangeLessThan(u64, 0, 10000));
        const z = @intToFloat(f64, random.intRangeLessThan(u64, 0, 10000));

        solutions[i] = Solution.init(x, y, z);
    }

    var i: i64 = 0;
    var generation: Generation = solutions;
    while (i < MAX_NUMBER_OF_GENERATIONS) : (i += 1) {
        std.debug.print("=== GEN {d}\n\n", .{i + 1});

        std.sort.sort(Solution, &generation, void, sortSolutionsInReverseOrder);

        std.debug.print("=== Best solutions\n", .{});
        for (generation[0..NATURAL_SELECTION]) |solution| {
            std.debug.print("{s}\n", .{solution.toString()});
        }
        std.debug.print("\n\n", .{});
    }
}