Horrors in C!

random_punter_2

Hi All,

I have spent hours doing this Genetic Algorithm but I cannot seem to get it working. It compiles right now, but the overall fitness does not increase like it should. I think it is the roulette wheel selection that may be at fault, or else its my array passing. I have built all the functions, alas I am at a loss. It's for a college submission on Artificial Intelligence, the ability to code is not the subject, if anyone could help figure out the problem I will give them a 10'er by paypal. It's frustrating being so close and yet so far!

http://pastebin.com/5mBUpsHc

Sparks

From the charter:

Evil Phil wrote: »

If you are a learning to code in college, in your first job or just out of interest here are the rules for beginners when asking questions:

• Try and give a good description of your problem in the thread title.
• Post a sample of your code no matter how poor you may think it is. It shows an effort on your behalf and that's really important
• Try and explain your attempt in the previous point
• Now ask any questions you may have
• If there are any errror codes, messages, or a stack trace then post that too. I might look like gobbledegook to you but it contains everything you need to know to solve your problem.

Follow these rules everywhere, here, on other forums, in work, in college and anywhere else you can ask a question. A willingness to learn to very important in development and nobody will fault you for asking a question as long as you've made a prior effort.

I mean, it's a bit hard to help you if you don't post any code at all...

ressem

Code from the pastebin link

the population array is numOfIndividuals {10} in size. r is incremented until runningTotal >= randomMedium

Which means population[r] soon starts accessing random values beyond the end of the array. Should it be population[r%numOfIndividuals].fitness?

Otherwise r can be in the hundreds, and population[r].fitness can be in the millions as it's not a value out of your dataset.

...
              int r=0;  //reset temporary total
              int runningTotal = 0;   //reset temporary total

              while (runningTotal < randomMedium)  //while our array sum is less than the random number
              {

                      r++;      //increment array position and try again
                      runningTotal += population[r].fitness;      //This adds the fitness value to the running total

 
              }

random_punter_2

Wow, thanks for the reply, ressem.

I presume the r%numOfIndividuals.fitness keeps the value within the array range. Nice. I recently had a problem where I would build up garbage data after a while and maybe this will help with that, I thought I had to initilise arrays and other such things. With regards to increasing the roulette wheel selection fitness, do you think it is working as it should? Do you see any problems with it? It doesn't seem to help my issue in that even after generation 100 the final finess of the genes is growing towards all 1's which is what it should.

Sparks, sorry about the lack of detail. The original requirement was to build a genetic evolution algorithm. In summary it should:
Generate a population with a certain number of "genes" (really just an array of random binary data).
Once the population is picked I need to use Roulette Wheel Selection to determine a new set of parents.
In the new parents we select a random cross over point and swap the genes from two parents into a child. We create a whole new population this way.
After that we have gene mutation where the gene just gets randomly flicked from 1 to 0 depending on the degree of mutation required.

At the moment I have tested everything, the random array is working, as is crossover and mutation, I seem to be having trouble with the roulette wheel selection. Any other ideas or suggestions?

Rockn

I don't think your roulette code is right.

for (int c=0; c<numOfParents; c++)   
           { 
         
                  int randomMedium = rand() % totalFitness;  //generate random point between 0 and the sum of all fitnesses 
                  int r=0;  //reset temporary total 
                  int runningTotal = 0;   //reset temporary total 
                
                  while (runningTotal < randomMedium)  //while our array sum is less than the random number 
                  { 
 
                          r++;      //increment array position and try again 
                          runningTotal += population[r].fitness;      //This adds the fitness value to the running total 
 
 
                  } 
                          tempParents[c]=population[r]; 
                    
           }

You're choosing a random number and then adding up the individuals fitnesses until you reach that number. Whatever individual you finish on becomes the parent. So basically you're just choosing random parents, you're not selecting the fittest ones.

random_punter_2

Thanks for the reply,

The way roulette wheel is meant to work is that you sum the fitness of all the population, then you pick a random number between 0 and that number. Then you count along the array until you get to that number and mark that position as a parent. Then you pick a random number again and start the process again. The theory is that the higher fitness individuals have a higher chance of being chosen, but for some reason this is not really happening.

http://www.edc.ncl.ac.uk/highlight/rhjanuary2007g02.php

The link given an idea of how it should work in a graphial form. The thing is its the crux of the algorithm, but for whatever reason its not picking the higher fitness parents, as far as I can tell

ressem

Yep.
Apart from the poor guy placed in population[0] who gets skipped over every time.
r++ in the wrong place? Which is why your runningTotal is sometimes still under the randomMedium despite being the sum of the other values of population[1] to population[9] (and a pile of 0's and other stuff for r> numOfIndividuals ).

Rockn

Just counting along the array to a random number will just give you random parents.

Looking at that roulete wheel page:
You need to give each individual a percentage chance of being selected based on it's fitness. The fitter it is the more likely it will be selected.

So say the total populations fitness is 50:
an individual with fitness 4 will have 4/50 * 100 = 8% chance of being selected
one with fitness 9 will have 9/50 * 100 = 18% chance etc.


Which leads to another problem. In the link they use a formula to calculate the fitness value which can never be zero. You just add up the ones, so if an individual has all zeros its fitness will be zero and it will have 0% chance of being selected. Which shouldn't happen.

ressem

No. OP's right.

The fitness value is equivalent to the number of lucky draw tickets they've got.
In order of population they put their tickets on the table from 0 to SUMOFFITNESSVALUES.

The rand() value if corrected will choose the correct person associated with the ticket.

I'm not so certain that children will approach perfect fitness though, though not bright enough to confirm. At a guess would think that it would average ~75% fitness.

Rockn

Yeah my mistake, I see how it works now.

fergalr

random_punter_2 wrote: »

Hi All,

I have spent hours doing this Genetic Algorithm but I cannot seem to get it working. It compiles right now, but the overall fitness does not increase like it should. I think it is the roulette wheel selection that may be at fault, or else its my array passing. I have built all the functions, alas I am at a loss. It's for a college submission on Artificial Intelligence, the ability to code is not the subject, if anyone could help figure out the problem I will give them a 10'er by paypal. It's frustrating being so close and yet so far!


http://pastebin.com/5mBUpsHc

Hey, just going to take you up on this for a second.

I had a quick look over the code (didn't go through it in huge detail).

Conceptually all the bits seem fine to me. I like how roulette wheel selection is done, hadn't heard of that before, very elegant way of getting individuals selected proportional to their fitness.


I'd ask the following, without testing the code myself: How do you know its not working? The population sizes you have in that code (10 parents, children) are very very small (and the mutation occurs very frequently too!) - how are you so sure its not selecting people proportional to their fitness (individual 0 aside, who is clearly broken), and its not just that your population is so small that what you see doesn't converge to the expected values, just due to statistics?

Now, I amn't saying thats the case, because I haven't even tried to test it, but I have to ask.


And that brings me to the bigger issue - you really seem to be making it hard for yourself, with how you've coded it.
Algorithms like this are somewhat hard to write, because it can be very easy to make an error and not see it.


For example, you've several different places in your code where you iterate across every individual, and calculate their fitness.
You should have a function to calculate an individuals fitness, which you call every time.
You should have a function to calculate the fitnesses of each member of the population, that you call every time.
(Maybe you'd even build these into a population object, and so on, but you seem to be trying to keep things lightweight).


This isn't an abstract 'code properly' piece of advice - doing things this way will make a real difference when you are trying to debug code like this, and save you more time than they take. (also, use variable names...)



And, seeing as you are writing code that is probabilistic in nature, you really need tests. That roulette wheel selection code, you need to write something that will confirm whether or not it is selecting individuals proportional to their fitnesses, without you having to figure this out analytically - in case you make a mistake.

Put the roulette wheel selection code into a function that returns an individual, proportional to the individual's fitness (as a % of the total fitness of the population).


And then write a simple test function that runs this code 100,000 times, and counts how many times each individual gets selected.

Output a table of the proportion of times each individual is selected, and the proportion of the total fitness they have.

This might seem like a bit of extra coding - but, if you think about it, its very straightforward, it should only take 15 minutes, and it means you'll know whether your code is working or not, you'll know when you fix the bug, and you'll know if you break it in future.


Its very hard to reason about whether code thats doing something probabilistic like that is working by just inspecting its output on a very small number of runs - whip up a quick test harness, and then you can be absolutely certain.

(I'd do this myself, but I have to eat :-) )


EDIT:
Just spent 15mins mucking around with it, after doing some writing.

Its subtle.
There are two problems that its hard to see.

int r=0;  //reset temporary total
int runningTotal =[B] population[0].fitness[/B];   //reset temporary total

while [B](runningTotal  <= randomMedium) [/B] //while our array sum is less than the random number
{
    r++;      //increment array position and try again
    runningTotal += population[r].fitness;      //This adds the fitness value to the running total
}

tempParents[c]=population[r];

Works now; but would have been very hard to realise the bug without a simple test harness - definitely test the component parts of the algorithm, as you build it, in future.

Capt'n Midnight

Sparks wrote: »

From the charter:


I mean, it's a bit hard to help you if you don't post any code at all...

http://www.ioccc.org/1994/smr.hint

random_punter_2

Hi All,

Thanks for the input. I did what a good coding friend told me to do, have a few beers and consider the topic with fresh eyes. It seems (from your comments) that the code does seem to work. In my virtualised version of Borland Builder the fitness does not get better, even after 300 generations the fitness of the mutated children can be 30. Its a weird one. I will battle on and report back soon. Thanks again...

fergalr

random_punter_2 wrote: »

Hi All,

Thanks for the input. I did what a good coding friend told me to do, have a few beers and consider the topic with fresh eyes. It seems (from your comments) that the code does seem to work. In my virtualised version of Borland Builder the fitness does not get better, even after 300 generations the fitness of the mutated children can be 30. Its a weird one. I will battle on and report back soon. Thanks again...

Did you read my comment? The code you pasted in does not implement roulette selection properly, as it stands.
You should write code to just test the roulette selection, by doing selection many times (eg 100k)
I provide the solution to the bug.

Naikon

random_punter_2 wrote: »

Hi All,

I have spent hours doing this Genetic Algorithm but I cannot seem to get it working. It compiles right now, but the overall fitness does not increase like it should. I think it is the roulette wheel selection that may be at fault, or else its my array passing. I have built all the functions, alas I am at a loss. It's for a college submission on Artificial Intelligence, the ability to code is not the subject, if anyone could help figure out the problem I will give them a 10'er by paypal. It's frustrating being so close and yet so far!

http://pastebin.com/5mBUpsHc

I can't help you with the genetic Algorithm I am afraid, but I suggest you at least remove your code from a public pastebin. I could be wrong about this, but you are giving up ownership rights to this code once you place it in the public domain. There are problems of ownership which could arise. Anyone care to correct me if I am off the mark? Sorry, I am not a lawyer.

http://pastebin.ca/what.php

Capt'n Midnight

Naikon wrote: »

I can't help you with the genetic Algorithm I am afraid, but I suggest you at least remove your code from a public pastebin. I could be wrong about this, but you are giving up ownership rights to this code once you place it in the public domain. There are problems of ownership which could arise. Anyone care to correct me if I am off the mark? Sorry, I am not a lawyer.

http://pastebin.ca/what.php

unless they get you to sign up to a clause that they own your code then you still own it.

copyright exists from when the work was first fixed (written down or typed or filmed or whatever)

patents have to be kept secret beforehand

Naikon

Capt'n Midnight wrote: »

unless they get you to sign up to a clause that they own your code then you still own it.

copyright exists from when the work was first fixed (written down or typed or filmed or whatever)

patents have to be kept secret beforehand

Ok, I see. Man, I have been reading up about this stuff and it's ****ing confusing:( For example. If I implement hello world or some trivial search Algorithm that is well documented by simply changing the order of the operands/substituting variable names can I sue someone? I would imagine the code would need to be innovative before Copyright can be enforced? Surely everything written down isn't subject to copyright? I mean, I understand it protects expression, but does this apply if the expressed program/source is trivial in nature? What if I someone copied a simple solution of mine from a textbook exercise for example? Interesting stuff all the same. Didn't know about the berne convention before.

Eliot Rosewater

There's a difference between a copyright and a patent. A copyright protects a specific instance of an idea, whereas a patent protects the abstract idea itself.

So your particular version of Hello World is copyrighted and owned by you. If someone had a patent for Hello World then they would own the whole idea of making a program that outputted Hello World, and they, I presume, would be able to restrict your ability to make specific instances of the Hello World concept.

(Your specific copyright doesn't stop someone else independently coming up with the same thing, which is inevitable given the triviality of Hello World.)


I think it goes something like that anyway. You don't have to worry too much, you are a GNUer after all.

Capt'n Midnight

Naikon wrote: »

I would imagine the code would need to be innovative before Copyright can be enforced? Surely everything written down isn't subject to copyright? I mean, I understand it protects expression, but does this apply if the expressed program/source is trivial in nature? What if I someone copied a simple solution of mine from a textbook exercise for example? Interesting stuff all the same. Didn't know about the berne convention before.

copyright doesn't need to be inovative , it just needs to be original enough that someone else can't claim it's a derivitve of their work


http://articles.cnn.com/2002-09-23/entertainment/uk.silence_1_peters-edition-nicholas-riddle-john-cage-trust?_s=PM:SHOWBIZ


http://en.wikipedia.org/wiki/Bitter_Sweet_Symphony - note here that the lyrics were new and they had already got permission to sample music written before they and most of the audience were born. Copyight only exists for 50 years on broadcasts, so in 5 years time anyone could use old broadcast recordings of it.

Patents on the other hand have to be innovative like these
http://www.newscientist.com/article/dn965-wheel-patented-in-australia.html - the Wheel

http://www.newscientist.com/article/dn2178-boy-takes-swing-at-us-patents.html - using a swing to go sideways instead of back and forth

Look at the history of Microsoft (or Apple or IBM any big software company) and patents lawsuits and the sums involved, then look at the nature of the patents - it's rarely anything other than intellectual land grabs , Excel only exists because the inventor (of visicalc ?) didn't patent spreadsheets

Naikon

Capt'n Midnight wrote: »

copyright doesn't need to be inovative , it just needs to be original enough that someone else can't claim it's a derivitve of their work


http://articles.cnn.com/2002-09-23/entertainment/uk.silence_1_peters-edition-nicholas-riddle-john-cage-trust?_s=PM:SHOWBIZ


http://en.wikipedia.org/wiki/Bitter_Sweet_Symphony - note here that the lyrics were new and they had already got permission to sample music written before they and most of the audience were born. Copyight only exists for 50 years on broadcasts, so in 5 years time anyone could use old broadcast recordings of it.

Patents on the other hand have to be innovative like these
http://www.newscientist.com/article/dn965-wheel-patented-in-australia.html - the Wheel

http://www.newscientist.com/article/dn2178-boy-takes-swing-at-us-patents.html - using a swing to go sideways instead of back and forth

Look at the history of Microsoft (or Apple or IBM any big software company) and patents lawsuits and the sums involved, then look at the nature of the patents - it's rarely anything other than intellectual land grabs , Excel only exists because the inventor (of visicalc ?) didn't patent spreadsheets

OK. Making more sense now. I can't understand though why copyright applies to works that have no commercial value. I mean, if something that isn't original or sensitive enough to exploit, then why should it be given copyrightable status by law?
So, if I take a twitter post for example that states "today is a lovely day, time for coffee" from an author, and he can prove this, I am liable for damages? Surely everthing written down isn't subject to copyright. Can I copyright my boards posts?:pac:

fergalr

Naikon wrote: »

OK. Making more sense now. I can't understand though why copyright applies to works that have no commercial value. I mean, if something that isn't original or sensitive enough to exploit, then why should it be given copyrightable status by law?
So, if I take a twitter post for example that states "today is a lovely day, time for coffee" from an author, and he can prove this, I am liable for damages? Surely everthing written down isn't subject to copyright. Can I copyright my boards posts?:pac:

1) You don't need to 'copyright' something, by and large; its automatic.
And of course your boards posts could have copyright - to consider a more clearcut case - imagine if someone sticks a short story up on the writing forum?

2) You should read the boards T&Cs, which talk about ownership of content, if you are interested in how boards works. (in brief, you retain ownership of stuff, but, quite reasonably, grant them a license to display your 'work').

Naikon

fergalr wrote: »

1) You don't need to 'copyright' something, by and large; its automatic.
And of course your boards posts could have copyright - to consider a more clearcut case - imagine if someone sticks a short story up on the writing forum?

But copyrighted works aren't registered by default. Could I sue someone for lots of money if the work is unregistered and has no commercial value? Can I sue someone for taking this post and giving it away on cd's? Surely copyright only applies to works of value?

fergalr

Naikon wrote: »

But copyrighted works aren't registered by default. Could I sue someone for lots of money if the work is unregistered and has no commercial value? Can I sue someone for taking this post and giving it away on cd's? Surely copyright only applies to works of value?

As far as I know (IANAL) it applies regardless of whether the work has economic value.
However, what you can and can't sue for, and what the remedies might be might change based on the value.
The Irish copyright law is all online, and very readable. Even though its without the case law that is important, it's worth a look.
You could start here if you are curious:
http://www.irishstatutebook.ie/2000/en/act/pub/0028/index.html

Capt'n Midnight

Naikon wrote: »

But copyrighted works aren't registered by default. Could I sue someone for lots of money if the work is unregistered and has no commercial value? Can I sue someone for taking this post and giving it away on cd's? Surely copyright only applies to works of value?

http://boards.ie/terms/

You own all of the Material you post on Boards.ie and we do not claim ownership of that Material. However, we need your permission to be able to display that Material and in some cases to modify it for best display – for different browsers, for our mobile site, and so on.

Consequently, by posting any Material on or through Boards.ie, you grant us a limited licence to use, modify, publicly perform, publicly display, reproduce, and distribute such Material.

The licence you grant to us is non-exclusive, royalty-free and fully paid, sub-licensable, and worldwide. This licence applies only to use of the Material for the purpose of providing the Boards.ie service.

From time to time we may seek to use users' Material for the purpose of advertising or marketing Boards.ie. However we will not use your Material for this purpose without your prior express written permission.

You are responsible for making sure that you have all rights to what you post, including the rights necessary for you to grant the foregoing licences to same.

You represent and warrant that: (i) you own the Material posted by you or otherwise have the right to grant the licence set forth in this section, and (ii) the posting of the Material does not violate the privacy rights, publicity rights, copyrights, contract rights or any other rights of any person.

You agree to pay for all royalties, fees, and any other monies owing any person by reason of any Material posted by you to or through Boards.ie.

In order to ensure that threads and conversations are not disrupted, we do not generally remove Material which is uploaded to us. Consequently, you agree that your Material displayed on Boards.ie may continue to appear on Boards.ie, even after you have terminated your user privileges or have had your user privileges terminated by Boards.ie.

However, we understand that you may wish to remove certain types of original creative Material (such as your photographs, drawings, videos, short stories, architectural plans, poetry and the like) from time to time.

Consequently if for any reason you decide that you no longer wish to have your original creative Material displayed on Boards.ie then we will delete it provided that this does not have a significant negative impact on the structure of the thread it features in. For example, we will not delete a work put up for constructive criticism as to do so would make the posts which respond meaningless.

these conditions are a lot more lenient than other services which claim copyright over all user content

fergalr

Capt'n Midnight wrote: »

http://boards.ie/terms/

these conditions are a lot more lenient than other services which claim copyright over all user content

Other services, such as..?
I know a few have tried, but isn't it usually quite controversial if they do? I'd say most companies offering communication services probably do it similar enough to boards.