Evolutional Algorithms DRAFT

#################################################################################################
#                                               #
# This is a really simple framework for solving evolutional algorithms              #
# This script was made for academic-only usage. You shouldn't use it on production evironments  #
# because most things here are experimental.                            #
# Author: Sergio Milardovich <[email protected]>                 #
# Licence: GNU/GPL (http://www.gnu.org/licenses/old-licenses/gpl-2.0.html)          #
# THIS PROGRAM IS FREE SOFTWARE.                                #
#                                               #
#################################################################################################
class Genetics
    attr_reader :iterations, :population, :population_count, :obj_sum

    def initialize

        # This variable works just as a buffer. It is used in the roulette function
        @buffer = []

        # Number of individuals
        @population_count = 50
        # Lenght of every individual
        @population_lenght = 23

        @population = []
        # In this array you should put the values which an individual can take (by default is 0,1)
        @population_dictionary = [0,1]
        # This array contains the probability of each element to be chosen
        @population_obj_rate = []

        # Mutation probability
        @mutation_rate = 0.05
        @mutation_type = "inversion"

        # Crossover probability
        @crossover_rate = 0.75
        @crossover_type = "one-cut"

        @obj_const = (2.0**30)-1
        @obj_sum = 0.0

        # Eltisim function
        @elitism = false
        # Number of elements passed by elitism
        @elitism_count = 0

        # Tournament function
        @tournament = false
        # Number of participants
        @tournament_participants = 0

        @selection_method = "roulette"

        @iterations = 200


    end

    def generatePopulation
        @population_count.times {
            |i|
            @population_lenght.times{
                | k |
                unless @population[i]
                    @population[i] = [@population_dictionary[rand(@population_dictionary.length)]]
                else
                    @population[i] << @population_dictionary[rand(@population_dictionary.length)]
                end
            }
        }
        self.makeObjRateArray
    end

    def doCrossover(index,start,c_end)
        buffer = @population[index].clone
        start.upto(c_end){
            |i|
            @buffer[index][i] = @buffer[index+1][i]
            @buffer[index+1][i] = buffer[i]
        }
    end

    def checkMutationByInversion(index)
        @population_lenght.times{
            | i |
            if rand(0.0..1.0) <= @mutation_rate then
                self.doMutationByInversion(index,i)
            end
        }
    end
    def doMutationByInversion(index,chromosome)
        if @population_dictionary.count == 2 then
            if @population[index][chromosome] == @population_dictionary[0] then
                @population[index][chromosome] = @population_dictionary[1]
            else
                @population[index][chromosome] = @population_dictionary[0]
            end
        end
    end

    def getObjFunction(index)
        return (@population[index].join().to_i(2)/@obj_const)**2
    end

    def getObjSum()
        @obj_sum = 0
        @population_count.times{
            |i|
            @obj_sum = @obj_sum+self.getObjFunction(i)
        }
        return @obj_sum
    end

    def checkObjSum()
        self.getObjSum()
        check = 0
        @population_count.times{
            | i |
            check = check + (self.getObjFunction(i)/@obj_sum)
        }
        return check
    end

    def makeObjRateArray()
        self.getObjSum()
        @population_count.times{
            | i |
            @population_obj_rate[i] = [i,(self.getObjFunction(i)/@obj_sum)]
        }
    end

    def findMaxObj()
        max = 0
        @population_count.times{
            | i |
            if self.getObjFunction(i) >= self.getObjFunction(max) then
                max = i
            end
        }
        return self.getObjFunction(max)
    end

    def findMaxFitness()
        return self.findMaxObj()/@obj_sum
    end

    def roulette
        self.getObjSum()
        @buffer = @population.clone
        # This small script will choose a new element using the probabilities from the array @population_obj_rate
        @population_count.times{
            | i |
            target = rand
            new_element = @population_obj_rate.find { |x, weight| target -= weight; target < 0 }.first
            @buffer[i] = @population[new_element].clone

            case @mutation_type
                when "inversion"
                    self.checkMutationByInversion(i)
            end

        }

        ((@population_count)/2).times{
            | k |
            if rand(0.0..1.0) <= @crossover_rate then
                case @crossover_type
                    when "one-cut"
                        self.doCrossover(k*2,rand(@population_lenght-1),@population_lenght)
                    when "two-cuts"
                        c_start = rand(@population_lenght-1)
                        self.doCrossover(k*2,c_start,rand(c_start,@population_lenght))
                end
            end
        }

        #if @elitism == true then
        #   self.elitism()
        #end
        @population = @buffer.clone
        self.makeObjRateArray()
    end

    def selectPopulation
        case @selection_method
            when "roulette"
                self.roulette
        end
    end

    def doElitism
        bestElements = @population.map {|bin_str| bin_str.join().to_i(2)}.sort.last 2

    end


#   def runTest
end