1
$\begingroup$

I am using the Fceux emulator to create a Genetic Algorithm in Lua to play the 'Arkanoid' game. It is based on Atari Breakout.

A member of my population contains a string of 0's and 1's.(Population size:200). Consider a member Every 10 frames a bit is read from the string.(Length of string is about 1000) If it is 0 the paddle moves left, If it is 1 the paddle moves right for the next 10 frames.

Now I wrote an genetic algorithm that tries to find the best sequence of inputs to play the game.

I have experimented with three types of fitness, One is to achieve maximum score, one is to try to reduce number of blocks to a minimum and the last one is to try to stay alive as long as possible.

None of the three fitness seem to work.

Then I thought that something with my crossover might be wrong.

Every generation, I print out the average fitness of all members. Some generations it increases, while in some generations it decreases. I have tried changing the population size to 50,100,200,300.

Mutation in my algorithm has a 1% Chance(If Mut_rate=1) that each of the bit will be replaced with its opposite bit.

Now coming to the crossover, I have used yet again many methodologies. One of them is to just select the top 20% or 30%(cr_rate)(according to their fitness) to pass on to the next generation and killing the remaining ones.

Another method is to add the top percentile to the population and use the remaining population to swap a few bits with top ones and add them into the next generation.

function crossover(population,rate)
    local topp=math.floor(rate*(#population));
    top={}
    for i=1,topp do
        table.insert(top,population[i])
    end
for i=1, #population do
        local p1 = math.random(1,topp);
        local p2 = math.random(1,topp);
        --print(top[p1]);
        --print(top[p2]);
        if top[p1][2] == top[p2][2] then
            local rval = math.random(1, 10) > 5;
                if rval then
                    population[i] = top[p1];
                else
                    population[i] = top[p2];
                end
            elseif top[p1][2] > top[p2][2] then
                population[i] = top[p1];
            else
                population[i] = top[p2];
        end
        population[i][2]=0;
end
--[[
for i=topp+1,#population do
    local p1 = math.random(1,topp);
    local p2 = math.random(1,#population);
    local s='';
    local flag=0;
    s=string.sub(top[p1][1],1,no_controls/2)..string.sub(population[p2][1],(no_controls/2)+1,no_controls);
    population[i][1]=s;
    population[i][2]=0;
 end
  --]]
end

Population is the table of population where each member has an input string and a fitness value.(Sorted , max fitness is first). Rate is the percentage to select the top performers. no_controls is the size of input string. The commented section of the code is where I perform the swap.

Here is the mutation function.

function mutation(population,mut_rate)

    local a=0;
    local b=1;
    for i=1, #population do
        for j=1, #(population[i][1]) do
            if math.random(1, 100) <= mut_rate then
                if string.sub(population[i][1],j,j)=='1' then
                population[i][1] = string.sub(population[i][1],1,j-1)..a..string.sub(population[i][1],j+1);
            else
                population[i][1] = string.sub(population[i][1],1,j-1)..b..string.sub(population[i][1],j+1);
            end
            end
        end
    end
end

Mut_rate is 1. And crossover rate is 0.2 or 0.5.

I have tried changing the mutation rate from 0 to 20. I have also tried to change the crossover rate as 0.2,0.5,0.7. And the fitness using no_blocks, score, time_alive. When I run the algorithm, the average fitness of the population first increases slightly , then decreases after a few generations and then remains constant forever.

The paddle also seems to be performing the same moves over and over again, which made be think that there might not be enough variation.

I need help, because I have been stuck on this for a few days now. I need suggestions on what would be a suitable crossover and mutation function and a perfect fitness function.

Thanks.

$\endgroup$
  • 1
    $\begingroup$ What you call a crossover sounds like a selection (likely close to the truncation selection). I may be wrong, but check your implementation and/or understanding. Apart from that, when the average fitness across the population stops changing it most likely means that the population has converged to a very small region of the search space and now consists of very similar individuals. $\endgroup$ – werediver May 31 '18 at 9:08
  • $\begingroup$ Hey, thanks for the reply, if you look closely at the crossover code, i have commented out a section there. That crosses over some members with members of population which adds some variation. and with mutation I think the similar individuals should dissapear slowly. $\endgroup$ – Surender Harsha Jun 2 '18 at 15:48
  • $\begingroup$ Selection pressure leads to convergence, unless you select for diversity (novelty search). Convergence on a local optimum is a common problem with generic algorithms. Your may try to mitigate this by enlarging the population size and/or increasing mutation rate (crossover is not considered to be an explorative operator). $\endgroup$ – werediver Jun 2 '18 at 16:18
  • $\begingroup$ Increasing the mutation rate, causes the population to become more random, thereby decreasing the average fitness. I have tried using a population of 400. But it still doesn't make a difference. Even though it has nothing to do with crossover, I think selecting the right crossover method will help to converge to an optimal solution faster. $\endgroup$ – Surender Harsha Jun 3 '18 at 17:10
  • $\begingroup$ A high average fitness should not be the goal, because it provides no guarantees about the best solution present, which is usually the most interesting, and a low average fitness does not mean you don't have great solutions. A higher mutation rate will bring you more diversity, thus raising chances to get into a good area of the search space, that's it. A larger population size does the same (don't put duplicates in the initial population). $\endgroup$ – werediver Jun 3 '18 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.