Premature Convergence

[marjorie...@uconn.edu]

Hello again!

My NSGA2 algorithm is getting premature convergence, so I am hoping for suggestions on parameters to tweak that would improve the search. In particular, it is not doing well finding solutions for the outer ranges of my objectives. My algorithm is set up to investigate land use planning outcomes, specifically for protected land networks. Each solution is a binary string which indicated whether a property is included in the protected lands network or not (0= not included, 1 = included). The fitness of each solution is based on geospatial analyses of the properties that are included in the solution (i.e., what do we get if we were to buy all the 1's). 

I'm working at fairly large landscapes so the solutions are binary strings with 16,400 elements (one for each property under consideration). I have not had this problem when I've worked with smaller spatial scales. I am using inspyred's uniform crossover operator.  I've tried increasing the mutation rate from 0.05 to 0.1 and 0.2, with no improvements to the solution space being explored. I figured I would reach out before trying any additional changes to my script.

Let me know if their is any information that I've left out that would be helpful!

Thanks,

Mauri

[James Arruda]

What is the size of your population? It maybe that you don't have a large enough population to adequately explore the solution space.

One thing that can also help is you can place all zeros and all ones as members of the first population (or any solutions you know would live near the single-objective optima). Or you can run single-objective GAs to try to find the corners of the frontier and use those points in the initial population. 

James

[marjorie...@uconn.edu]

I've been using populations of 50. 

So for the alternative first population you propose, there would be no random selection of individuals and only individuals with all ones or zeros?

-Mauri

[James Arruda]

I would suggest having a large set of randomly selected individuals, plus several selected individuals that are in known important regions of your objective space. Then adding one chromosome of all zeros and one of all ones to the set. The reason for that is to try to find some extreme pareto-optimal solutions that will stick around throughout the evolution and reproduce with other solutions. It's the same idea as you had with increasing the mutation rate for diversity, except we're forcing the diversity up front. 

Thinking of the 16,400 binary choices, if you're uniformly selecting bit flips at the start, it's highly unlikely to get much diversity above and below 50% of the bits being on and off. Scipy.stats is telling me that the probability of seeing more than 8500 bits being '1' is 1.342...e-06 (that's only 51% of bits being on). Having a population of size 50 makes finding those more extreme points randomly a more difficult.

I've seen recommendations of having the population count be near or greater than the length of your chromosome, but that's for much smaller problems. I'd say try something in the several hundreds and see if that helps. I wish I knew some papers offhand that had recommendations for parameter settings for such a large problem.

Hopefully someone else on the mailing list can provide better insight or papers to guide the parameter selection.

James

--
You received this message because you are subscribed to the Google Groups "Inspyred" group.
To unsubscribe from this group and stop receiving emails from it, send an email to inspyred+u...@googlegroups.com.
To post to this group, send email to insp...@googlegroups.com.
Visit this group at https://groups.google.com/group/inspyred.
For more options, visit https://groups.google.com/d/optout.

[marjorie...@uconn.edu]

Thanks for these great suggestions! I will try to remember to report back on what ends up working the best!

Cheers, 

Mauri

[marjorie...@uconn.edu]

So I've tried three different things so far with limited results:

1) Increase the mutation rate (up to 0.3)

2) Change the seed population so that 20-30% are solutions with all zeros, all ones, or an optimal outcome for 1 of 6 objectives that I am particularly interested in

3) Increase my population size (200-800; chromosome length is 676 bits)

The algorithm does a little bit better at finding the extreme values for my objective but still not good enough. I also suspect that the algorithm is getting stuck in local maximums and not getting close enough to the true frontier. I've been using the default operators for the NSGA2 algorithm (inspyred.ec.emo.NSGA2) which are listed as crowding for the replacer and a binary tournament for the selection. I was thinking I would try different replacer and/or selection operators next but am open to suggestions. 

[marjorie...@uconn.edu]

Does anyone have any other suggestions I should try? Nothing that I've thrown at this seems to make a difference. 

[Mark Coletti]

On Fri, Jun 8, 2018 at 10:45 AM <marjorie...@uconn.edu> wrote:

Does anyone have any other suggestions I should try? Nothing that I've thrown at this seems to make a difference. 

On Monday, June 4, 2018 at 4:43:35 PM UTC-4, marjorie...@uconn.edu wrote:

So I've tried three different things so far with limited results:

1) Increase the mutation rate (up to 0.3)

2) Change the seed population so that 20-30% are solutions with all zeros, all ones, or an optimal outcome for 1 of 6 objectives that I am particularly interested in

3) Increase my population size (200-800; chromosome length is 676 bits)

There are two places selection happens: parent selection and survival selection.  You mention using binary tournament selection -- is that for parent or survival selection?  And what other selection strategy are you using?  It could be that the other selection strategy you've chosen is too greedy; e.g., truncation selection.

-- Mark 

[Aaron Garrett]

I admit that I don't entirely understand the problem you're trying to optimize. Is it true that there's a sort of 2D layout to the meaning behind the bits of the chromosome?

The previous suggestions focused on the fact that your search space is HUGE, and the likelihood of getting anywhere near the optimal frontier is vanishingly small with coin flips. The selection and replacement schemes can keep the population on a good path if it finds one, but I think in this case you might find more success if you revisited your mutation/crossover operators. The off-the-shelf operators don't presume any knowledge of the problem. They're pretty generic. But if there's an inherent structure to your problem that an operator could exploit, then that operator would move through the space better. For example, suppose that there were some 2D representation of a chromosome, where some bits were adjacent to others on a grid, and suppose that we knew, generally, that better solutions tend to have "clumps" of 1 bits. Then we could define a mutator that flipped a particular bit to look more like its 2D neighbors with a higher probabilty than to flip it to look less like them. That's just a silly example, but maybe it illustrates what I'm trying to describe.

Good variation operators move through the search space efficiently, and they always exploit some information about the problem domain and representation.

If you can give more details about your problem representation, I might be able to come up with something to try.

On Fri, Jun 8, 2018 at 10:45 AM <marjorie...@uconn.edu> wrote:

--

Aaron Garrett, Ph.D.

Assistant Professor

Computer Science

Wofford College

429 North Church Street

Spartanburg, SC 29303

garr...@wofford.edu

(864) 597-4529

[marjorie...@uconn.edu]

I am trying to find acquisition solutions for properties (range 90-700) on a landscape. I have represented these properties with a 1D binary chromosome. In reality, there is a 2D layout to the properties (although not in a uniform grid) so your 'silly example' is not that far off. I am trying to find solutions (i.e., properties to buy) that optimize a 6-objective problem. The value of each objective and therefore the fitness of the solution is dependent on which parcels are purchased (1 bits) and which are not (0 bits) in a given chromosome.

The algorithm had been doing fine with shorter chromosomes (n=96) but has struggled with the longer chromosomes (n=676). 

Currently, my variators are a Uniform Crossover and Bit Flip Mutation with an 0.8 mutation rate. I am using NSGA2 so my operators are:

ea = inspyred.ec.emo.NSGA2(prng)

variator = [inspyred.ec.variators.uniform_crossover, 

               inspyred.ec.variators.bit_flip_mutation]

observer = custom

terminator = inspyred.ec.terminators.generation_termination

evaluator = custom that uses inspyred.ec.emo.Pareto

pop_size = 800

seeds = custom that includes random chromosomes and a few that are all zeros and all ones

maximize = True (objectives are maximized and minimized but are specified with a Boolean list in the evaluator)

nr_inputs = number of bits/parcels in the chromosome

max_generations = 500 (but have tried longer too)

mutation_rate = 0.8

I'm happy to share the full script if that would be helpful.

Thanks!

-Mauri

Your 'silly example' is actually a very applicable example.  

[Aaron Garrett]

If you're comfortable sharing the script to the forum, I think it would help to see it. If you're not comfortable with it being public, you are welcome to send it directly to me (aaron.le...@gmail.com).