Implementing multi objective evolutionary optimization with custom input variables

[Vibes S.]

Hi, 

I am trying to implement multi objective problem for a hypothetical problem with following details, but not sure how to code it up

Input population (~100-1000s) needs to be distributed between multiple islands (~10-20) but the population are shared among these islands. 

- There are multiple factors that depends on sum of subset of population on each island that contributes to objective function.

a) input variables x[0], x[1], x[2], x[3]...x[100] need to be distributed among 10 islands

x[0][0] + x[1][0] + ... + x[100][0] is allocated to island 0

x[0][1] + x[1][1] + ... + x[100][1] is allocated to island 1 

...

x[0][1] + x[1][1] + ... + x[100][1] is allocated to island 9

All these variables are integer variables (I am not sure how to code integer constraints)  

b) Equality constraint : Sum of all allocated would be same as input 

x[0][0] + x[0][1] + x[0][2] + ... + x[0][100] = x[0]

c) Inequality constraints: Each variable each island has constraint of their own like 

x[0][0] < 1000 

x[0][1] < 50000

d) Aggregate constraints on subset/fraction of population: There are aggregate constraints for each island

x[0][0] + x[0][10] + x[0][11] < sum of all quantities island 0 gets 

e) some more similar constraints

There is a cost associated with each island that needs to be minimized, each objective function is quite complex, something like below: 

f_island0(x) = x[0][0] * 1 + x[1][0] * 2 + ... x[2][0] * 2 + ... x[100][0] * 5 (predefined factors) + ( x[0][1] + x[0][2] ) * 3 . ... .

These look too complex, could you let me know if you think it is possible to implement this? 

[Aaron Garrett]

You're losing me in the notation a bit. Are you saying that you want to use an island model but that the fitness for an individual on some particular island depends on what is happening on the other islands?

--
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.

--

Aaron Garrett, Ph.D.

Assistant Professor

Computer Science

Wofford College

429 North Church Street

Spartanburg, SC 29303

garr...@wofford.edu

(864) 597-4529

[Vibes S.]

I might be wrong in the notation, but you are right, individual on particular island depends on what is happening on other islands. 

If on one island for variable x[0] the quantity increases, on other islands it is supposed to reduce, to keep total x[0] constant, but should minimize total cost/ objective function on all islands. 

Rephrasing the constraints if this makes more sense, I corrected d) to show only quantities in bucket 0 

a) input variables x[0][0], x[0][1]....x[0][9], x[1][0] .... x[1][9], ...x[100][9] (total 100x10 input to be distributed between 10 buckets, b) defines the max quantities)

x[0][0] + x[1][0] + ... + x[100][0] is allocated to bucket 0

x[0][1] + x[1][1] + ... + x[100][1] is allocated to bucket 1 

...

x[0][1] + x[1][1] + ... + x[100][1] is allocated to bucket 9

All these variables are integer variables. 

b) Equality constraint : Sum of all allocated would be limited to quantity of x[0] 

x[0][0] + x[0][1] + x[0][2] + ... + x[0][100] = x[0] (where x[0] is constant value like 2000 or 4000)

c) Inequality constraints: Variable in each bucket has constraint of their own like 

x[0][0] < 1000 

x[0][1] < 50000

d) Aggregate constraints on subset/fraction of population in bucket 0: 

x[0][0] + x[0][10] + x[0][11] < 10% of sum of all quantities bucket 0 

objective function to be minimized: 

f_bucket_0(x) = x[0][0] * 1 + x[0][1] * 2 + ... x[0][1] * 2 + ... x[0][100] * 5 + ( x[0][1] + x[0][5] ) * 3 . ... 

where 1,2,2,...5,3 are predefined factors that includes

a) Factor on each quantity - x[0][0] * 1 + x[0][1] * 2 + ... x[0][1] * 2 + ... x[0][100] * 5 

b) Factor on aggregate of quantities: ( x[0][1] + x[0][5] ) * 3, etc 

[Aaron Garrett]

It's not clear to me what an island model approach has to do with your problem then. Let me make a simplified version of my understanding of your situation...

You have 15 total inputs and want to split them among 5 groups (3 in each). So let's arrange them as a 3x5 grid.

x00  x10  x20

x01  x11  x21

x02  x12  x22

x03  x13  x23

x04  x14  x24

You also have a whole host of constraints on columns, rows (or subsets of rows), and individual elements. And your task is to optimize some big linear combination of the 15 elements.

So, my question remains... why do you think you need an island model for this problem? Usually, an island model is used if you have different populations that can evolve independently and share information periodically. Yours can't really evolve independently because each "solution" is the entire 15-element thing, and that whole thing is subject to some kind of "cross-island" constraints. The fact that you imagine rows as being in "buckets" that are separated from other rows doesn't matter. They're clearly not really separated because they can't change without affecting some other "bucket".

You basically have something like a sudoku problem, as best I understand it, but without the permutation constraints. So, my first suggestion would be to see what approaches have been used to solve sudoku puzzles. There's tons of information that will be really easy to find and understand. Some of those might immediately look promising for your situation.

If I were going to work this problem straight, I would think about representing my simple example as a 15-element list of integers. Each one is pulled from and bounded to its individual constraint bounds. And then you can check the subset (or whatever) constraints in the evaluation and penalize any solutions that violate a constraint by some amount, in order to make sure legal solutions have better fitness values.

Does any of that make sense?

[Vibes S.]

Thank you for your reply. Yes, you are right. 

The reason I was trying to use multi objective/ evolutionary approach was to find a solution that can be improvised in subsequent iterations and would evolve towards minimum objective functions. Similarly the thought around islands was to have a feature to run each island in parallel but it does not look to be applicable to this problem considering both rows and columns are related. 

 

I am not sure of solution to Sudoku like problems that would be able to solve problem size of (~100 to 1000 variables and ~100 constraints per row). I will try searching around evolutionary and parallel approaches for this problem.