GA Help Needed Urgently
Hi,
I'm stuck on how exactly to define the selectParent() method (the Selection method) because I have to take out samples of size 5 (the tournament size) from the population and then order those chromosomes ( in the contenders ArrayList) in order of fitness (the lower the fitness the better). But since I'm working with ArrayLists and since I have to extract each Chromosome object from the contender Arraylist, somehow call the fitness() method on each Chromosome, and then sort in order of fitness (lowest first), then store the 2 Chromosomes with the lowest fitness into a parent ArrayList, I'm lost with how to do this. Any ideas on this please? What's the simplest way of doing it?
Here's the code I have done - the commented stuff is the stuff I have tried to code to do the sorting, but it's all useless now. I am almost in a giving up situation here - Can anyone come up with a solution for how the tournament selection sort would be done in order for my code to run - or some sort of sorting algorithm to order the fitness from lowest to highest as this is the part I am find most trouble with - the thing I don't understand is that because the fitness value of each Chromosome is not stored anywhere (like a variable or ArrayList), how am I able to order the fitnesses from every sample of 5? PLEASE HELP URGENTLY :-(
import java.util.ArrayList;
import java.util.Random;
import java.util.Collections;
import java.math.*;
import java.util.Collection;
class Population{
Database d =new Database();
Random rand =new Random();
ArrayList population =new ArrayList();
ArrayList parents =new ArrayList();
ArrayList contenders =new ArrayList();
publicvoid initialPopulation(){
double[] reuters ={
8.0, 9.0, 12.5, 11.5, 6, 7, 4, 2, 3, 4, 3, 5, 5.5};
Share s1 =new Share(reuters);
d.addShare(s1);
for (int i = 0; i < 10; i++){
Chromosome c =new Chromosome(rand);
c.setDatabase(d);
population.add(c);
System.out.println("Chromosome Weights are: " + c);
System.out.println("Chromosome Fitness Value is: " + c.fitness(0));
System.out.println();
}
System.out.println(population.size());
System.out.println(population.toString());
System.out.println();
//System.out.println(d);
}
public ArrayList selectParents(int tournamentSize){
// Get as many chromosomes as specified by tournament size
for (int i = 0; i < tournamentSize; i++){
contenders.add(i, population.get(i));
}
// Sort the sub-population in order of fitness *****Having Huge Problems Here***
/* double[] fitnessVals = new double[5];
double[] temp = new double[5];
ArrayList tempArrayList = new ArrayList();
for (int i = 0; i < (contenders.size()); i++) {
Chromosome temp1 = (Chromosome)contenders.get(i);
fitnessVals[i] = temp1.fitness(0); }
System.out.println((fitnessVals[0]) +","+ (fitnessVals[1]));
for (int i = 0; i < (contenders.size()); i++) {
if (fitnessVals[i] > fitnessVals[i+1])
{
temp[i] = fitnessVals[i + 1];
fitnessVals[i + 1] = fitnessVals[i];
fitnessVals[i] = temp[i];
tempArrayList.add(contenders.get(i + 1));
contenders.set(i+1, contenders.get(i));
contenders.set(i, tempArrayList.get(i));
}
else {}
//Collections.max((Collection)contenders.get(0));
// System.out.println(contenders.toString());
}
*/
/* public void sortInOrderOfFitness(Comparable ArrayList ) {
for (int i = 0; i < contenders.size(); i++) {
Collections.sort(contenders);
}
System.out.println(contenders); ****Up to Here is Where I'm Lost***
} */
// Return the best two
parents.add(contenders.get(0));
parents.add(contenders.get(1));
System.out.println(parents.toString());
System.out.println(contenders.toString());
return parents;
}
publicstaticvoid main(String args[]){
Population p =new Population();
p.initialPopulation();
p.selectParents(5);
}
}
import java.util.ArrayList;
import java.util.Random;
class Chromosome
{int[] bit =newint[12];
Database db;
Chromosome(Random rand)
{for (int i = 0; i < 12; i++)
{ bit[i] = rand.nextInt(6);}
}
public String toString()
{ String res ="";
for (int i = 0; i < 12; i++)
{ res = res + bit[i] +",";}
return res;
}
publicvoid setDatabase(Database d)
{ db = d;}
publicdouble fitness(int share)
{double prediction = 0;
int divisor = 0;
Share sh = db.getShare(share);
for (int i = 0; i < 12; i++)
{ prediction = prediction + bit[i]*sh.getPrice(i);
divisor = divisor + bit[i];
}
if (divisor != 0)
{ prediction = prediction/divisor;}
else
{ prediction = 0;}
System.out.println("Prediction Value is: " + prediction);
double actualPrice = sh.getPrice(12);
return Math.abs(prediction - actualPrice);
}
}
import java.util.ArrayList;
import java.util.Random;
class Database
{ ArrayList sharedata =new ArrayList();
publicvoid addShare(Share s)
{ sharedata.add(s);}
public Share getShare(int i)
{return (Share) sharedata.get(i);}
}
class Share
{double[] prices =newdouble[13];
Share(double[] p)
{ prices = p;}
double getPrice(int i)
{return prices[i];}
}
[9545 byte] By [
Niru99a] at [2007-11-26 23:37:03]
You shouldn't assume that everyone reading your post is familiar with your homework assignment.
> I'm stuck on how exactly to define the selectParent()
> method (the Selection method) because I have to take
> out samples of size 5 (the tournament size) from the
> population and then order those chromosomes ( in the
> contenders ArrayList) in order of fitness (the lower
> the fitness the better). But since I'm working with
> ArrayLists and since I have to extract each
> Chromosome object from the contender Arraylist,
> somehow call the fitness() method on each Chromosome,
> and then sort in order of fitness (lowest first),
> then store the 2 Chromosomes with the lowest fitness
> into a parent ArrayList, I'm lost with how to do
> this. Any ideas on this please? What's the simplest
> way of doing it?
What part are you having trouble with exactly? Determining how to evaluate fitness? Sorting the List?
If you have a given fitness evaluation algorithm (put it in a class) then you could easily write a Comparator that sorts by that evaluation, and then sort the list of chromosomes using Collections.sort. Then you could just take the first two chromosomes from the sorted list. But is that your problem?
Oh, I see that you're a cross-posting weasel: http://forum.java.sun.com/thread.jspa?threadID=5155367I should have checked first.
I didn't assume everyone reading this would be familiar which is why I supplied my code as well as give a detailed description to what I was finding difficulty with...and no I am not stuck on the fitness function as I have already defined it if you look at the code...but yes, I am finding difficulty with the sorting part of the tournament selection - and as I have already written previously in my post, I am finding a lot of difficulty in particular with how to order the fitnesses of samples of 5 Chromosomes of the population given that the fitness values are not stored anywhere, only returned within the fitness function method. Is it worth storing the fitness value in an actual variable for each Chromosome? The sorting algorithm is proving very difficult for me at the mo.
Yes, its quite an accomplishment for you to have realised that ;) - I wasn't receiving any replies and thought maybe I was posting in the wrong forums - I only signed up today as you may have noticed.
> I didn't assume everyone reading this would be
> familiar which is why I supplied my code as well as
> give a detailed description to what I was finding
> difficulty with...
It wasn't that detailed a description. "Rambling" might be a better word.
> and no I am not stuck on the
> fitness function as I have already defined it if you
> look at the code...
I did look at the code, but it wasn't clear whether you actually felt the fitness function was working or generally correct. You have to learn to express yourself more clearly.
> but yes, I am finding difficulty
> with the sorting part of the tournament selection -
> and as I have already written previously in my post,
> I am finding a lot of difficulty in particular with
> how to order the fitnesses of samples of 5
> Chromosomes of the population given that the fitness
> values are not stored anywhere, only returned within
> the fitness function method.
OK, so you'd sort based on the return values of the function. What's the problem?
> Is it worth storing the
> fitness value in an actual variable for each
> Chromosome?
Maybe, but it's not necessary. Is anything else going to care about the fitness value? Are you planning to need to look at the fitness values a lot, relative to the frequency at which the input to the fitness function changes?
Have you looked at the API docs for Collections.sort and Comparator?
> The sorting algorithm is proving very
> difficult for me at the mo.
It's easier than you think.
>
> It wasn't that detailed a description. "Rambling"
> might be a better word.
Funny, everyone else understood what I wrote which seems to me you weren't reading what I wrote properly.
>
> I did look at the code, but it wasn't clear whether
> you actually felt the fitness function was working or
> generally correct. You have to learn to express
> yourself more clearly.
I pasted the code, highlighted precisely which part I was stuck on, explained what I was stuck on, I thought this was clear enough...
> > but yes, I am finding difficulty
> > with the sorting part of the tournament selection
> -
> > and as I have already written previously in my
> post,
> > I am finding a lot of difficulty in particular
> with
> > how to order the fitnesses of samples of 5
> > Chromosomes of the population given that the
> fitness
> > values are not stored anywhere, only returned
> within
> > the fitness function method.
>
> OK, so you'd sort based on the return values of the
> function. What's the problem?
>
How to relate them back to the particular Chromosome
> > Is it worth storing the
> > fitness value in an actual variable for each
> > Chromosome?
>
> Maybe, but it's not necessary. Is anything else
> going to care about the fitness value? Are you
> planning to need to look at the fitness values a lot,
> relative to the frequency at which the input to the
> fitness function changes?
>
> Have you looked at the API docs for Collections.sort
> and Comparator?
I did briefly, didn't understand much though, will look again at them today
>
> > The sorting algorithm is proving very
> > difficult for me at the mo.
>
> It's easier than you think.
I hope so, I really need to get this thing working very soon. No better thing than perseverence I guess.
> Funny, everyone else understood what I wrote which
> seems to me you weren't reading what I wrote
> properly.
Everyone else being...?
> I pasted the code, highlighted precisely which part I
> was stuck on, explained what I was stuck on, I
> thought this was clear enough...
You said "having huge problems here" which doesn't tell me much other than that you had problems there. Also the code has the look of a series of unsuccessful unfinished attempts, which doesn't tell us much other than that you were trying to do something.
The first step in being able to solve problems like this is the ability to express what the problem is.
> > OK, so you'd sort based on the return values of the
> > function. What's the problem?
>
> How to relate them back to the particular Chromosome
You have an ArrayList of Chromosome objects. Right?
You want to sort that List, right?
Collections.sort will sort a List.
You can choose how the sort is done by using a Comparator, as you've been told. So I guess you don't understand how Comparators work. When compare() is called, it's passed two arguments. Those two arguments are elements from the list. Since you call it on a list of chromosomes, those two arguments must be chromosomes.
Is that what you were having trouble with?
> > Have you looked at the API docs for Collections.sort
> > and Comparator?
>
> I did briefly, didn't understand much though, will
> look again at them today
Well then ask about the parts you don't understand.
> > > The sorting algorithm is proving very
> > > difficult for me at the mo.
> >
> > It's easier than you think.
>
> I hope so, I really need to get this thing working
> very soon. No better thing than perseverence I guess.
It occurs to me that the way you phrased that may be telling. You don't have to worry about the sorting algorithm per se. That's all hidden behind the API. All you have to do is provide a way to compare two objects (i.e., a Comparator); the sort method uses that to do the sorting. If you have a fitness function, all you have to do is invoke it on the arguments, and then compare the results.
> No better thing than perseverence I guess.
There are lots of better things, like knowing when to take a break or let it be. Not a suggestion for ths specific issue, but generally.
By the way I didn't bother to read your posts, I just looked at the following discussions. Words like "urgent" turn me off pretty quickly.
> > No better thing than perseverence I guess.
>
> There are lots of better things, like knowing when to
> take a break or let it be. Not a suggestion for ths
> specific issue, but generally.
>
> By the way I didn't bother to read your posts, I just
> looked at the following discussions. Words like
> "urgent" turn me off pretty quickly.
Well I'm afraid I don't do things like 'let it be' given that I have to find a solution to this problem...and as for the posts, I'm not bothered if you read it all...however I would say that if you don't have any help to give, then don't write anything at all. With regards to why I wrote 'urgent' , I wasn't aware that this is considered rude as I really felt and still feel my issue is urgent...anyway just to reiterate, unless you are able to give some advice on the problem here I would strongly suggest you don't write in this thread..I will simply ignore it next time.
> Well I'm afraid I don't do things like 'let it be'
> given that I have to find a solution to this
> problem...
As I said, this was not advice to this specific situation. I just wanted to point out that persevering is very often *not* good.
> and as for the posts, I'm not bothered if
> you read it all...however I would say that if you
> don't have any help to give, then don't write
> anything at all.
I think I gave you advice to take a break if you sat at a problem for too long, and not to mark your posts as "urgent".
> With regards to why I wrote 'urgent'
> , I wasn't aware that this is considered rude as I
> really felt and still feel my issue is
> urgent...
If you're that new to internet fora, you might want to read this:
http://www.catb.org/~esr/faqs/smart-questions.html
Because it's not something that's in any way special to this board.
> anyway just to reiterate, unless you are
> able to give some advice on the problem here I would
> strongly suggest you don't write in this thread..I
> will simply ignore it next time.
Feel free to do so.
> You have an ArrayList of Chromosome objects. Right?
Yes
>
> You want to sort that List, right?
Yes in descending order of their fitness value (however the fitness value is not stored anywhere in the Chromosome)
>
> Collections.sort will sort a List.
>
> You can choose how the sort is done by using a
> Comparator, as you've been told.
Yes I am aware of that, but I have issues here, read below.
> So I guess you
> don't understand how Comparators work. When
> compare() is called, it's passed two arguments.
> Those two arguments are elements from the list.
> Since you call it on a list of chromosomes, those
> two arguments must be chromosomes.
>
> Is that what you were having trouble with?
Yes, and also how to call the fitness function on each Chromosome object in the contender Arraylist - I can't do (Chromosome) contender.get(i).fitness(0) - so I'm not sure how to extract each Chromosome from the ArrayList and then call the fitness function on that Chromosome? If I copy each Chromosome from the contender Arraylist to and store each Chromosome into another Chromosome object (so I would have 5 Chromosome objects in all as the contender Arraylist consists of 5 Chromosome objects), then call the fitness function on each of these Chromosomes from within the Class that implements Comparator, what would I do next? Am I on the right track here?
Also, why can I not implement the Comparable interface instead of the Comparator? I would be calling only the fitness function inside the class that implements Comparable (correct?), and if so, then fitness funtion returns a double. Or do I need to somehow reference the Chromosomes so that I know which fitness value belongs to which Chromosome (in which case I would have to use Comparator)? I am very unclear on this.
Guys, I have got my tournament selection to work (although it's only for share right now)! After extensively reading up on the Comparator and Comparable interface, and the Collections class, and after analysing my whole program in a lot of detail, I was able to answer all of my own questions which I wrote above(!). This forum is really proving useful :-)
I am going to make what I've done so far look a bit neater and wanted to know if /* */ is used exclusively at the beginning of the class to describe in general what the program does? Is // used for describing in brief how various parts like methods work within the program?
Haven't programmed for ages, I know this is a basic question, but simple yes or no to the 2 queries will be appreciated.
> Well I'm afraid I don't do things like 'let it be'
> given that I have to find a solution to this
> problem..
You'll find in this field that you'll often have a problem, giving you a choice that looks like this:
* Take a break for two hours, come back to the problem, see the solution immediately
* Continue working for six hours, and still not see the solution. Finally give up for the day, and when you come back the next day you finally see the obvious solution immediately.
The first option is faster.
> Yes, and also how to call the fitness function on
> each Chromosome object in the contender Arraylist - I
> can't do (Chromosome) contender.get(i).fitness(0) -
> so I'm not sure how to extract each Chromosome from
> the ArrayList and then call the fitness function on
> that Chromosome?
You don't have to do that at all. When the compare method is called, it is passed two objects to compare. You write the comparison code, using the fitness function in this case. Within the compare method, you already have the objects you need to call the function on -- no need to extract anything.
> If I copy each Chromosome from the
> contender Arraylist to and store each Chromosome into
> another Chromosome object (so I would have 5
> Chromosome objects in all as the contender Arraylist
> consists of 5 Chromosome objects), then call the
> fitness function on each of these Chromosomes from
> within the Class that implements Comparator, what
> would I do next? Am I on the right track here?
No you're making it far too complicated.
> Also, why can I not implement the Comparable
> interface instead of the Comparator?
Perhaps you can. Actually, usually it's better to do that if you can, because it provides better encapsulation. I just mentioned Comparators because they seem easier for newbies to grok.
> I would be
> calling only the fitness function inside the class
> that implements Comparable (correct?)
You would be invoking the fitness method from inside the compareTo method.
You would probably be invoking it twice (once for the this object, and once on the object passed as an argument).
>, and if so,
> then fitness funtion returns a double.
Yeah. So you'd be comparing two doubles, to determine which is bigger, and then returning a number that expresses that relationship (see the docs).
> Or do I need
> to somehow reference the Chromosomes so that I know
> which fitness value belongs to which Chromosome (in
> which case I would have to use Comparator)? I am very
> unclear on this.
I'm not even clear what you're asking here. You'll have two objects. If you're implementing Comparable, then you'll have a compareTo method and one of the two objects will be referenced with this, and if you're implementing Comparator then you'll have a compare method and each of the two objects will be passed as arguments. You'll know which is which because you can have local variables that will hold each resulting fitness value (if you like; actually you can simplify the code to the point where you don't even need local variables).
> Guys, I have got my tournament selection to work
> (although it's only for share right now)! After
> extensively reading up on the Comparator and
> Comparable interface, and the Collections class, and
> after analysing my whole program in a lot of detail,
> I was able to answer all of my own questions which I
> wrote above(!). This forum is really proving useful
> :-)
I should have read this post before I answered the above posts.
> I am going to make what I've done so far look a bit
> neater and wanted to know if /* */ is used
> exclusively at the beginning of the class to describe
> in general what the program does? Is // used for
> describing in brief how various parts like methods
> work within the program?
Generally, but there are no hard-and-fast rules about it. If you need a long comment in the middle of the program source code you can use /* */ comments.
Don't neglect your /** */ (javadoc) comments either. They make things even easier to read.
> Haven't programmed for ages, I know this is a basic
> question, but simple yes or no to the 2 queries will
> be appreciated.
Yes well, I didn't take a break today but after reading the stuff a few times, I was able to understand it and apply it to my program, so I don't think it quite fits in with any of the options you stated ;-) Got there in the end though..which is the main thing...
Great, thanks for your help :-)
