Genetic Algorithms

May need some advice

  • (2 Pages)
  • +
  • 1
  • 2

19 Replies - 5789 Views - Last Post: 27 December 2009 - 05:01 PM Rate Topic: -----

#1 spintronic  Icon User is offline

  • D.I.C Head

Reputation: -32
  • View blog
  • Posts: 94
  • Joined: 25-December 09

Genetic Algorithms

Posted 25 December 2009 - 12:07 PM

I was hoping to write a genetic algorithm in C++, but before I started, I was wondering is there's any existing code I could modify, before starting from scratch?
Is This A Good Question/Topic? 0
  • +

Replies To: Genetic Algorithms

#2 PsychoCoder  Icon User is offline

  • Google.Sucks.Init(true);
  • member icon

Reputation: 1659
  • View blog
  • Posts: 19,853
  • Joined: 26-July 07

Re: Genetic Algorithms

Posted 25 December 2009 - 12:09 PM

That way you dont have to really do anything? come on, this isnt a place where we're going to hand out source code so a student can "alter" it to fit their needs, then turn it in as their work.
Was This Post Helpful? 0
  • +
  • -

#3 spintronic  Icon User is offline

  • D.I.C Head

Reputation: -32
  • View blog
  • Posts: 94
  • Joined: 25-December 09

Re: Genetic Algorithms

Posted 25 December 2009 - 12:11 PM

View PostPsychoCoder, on 25 Dec, 2009 - 11:09 AM, said:

That way you dont have to really do anything? come on, this isnt a place where we're going to hand out source code so a student can "alter" it to fit their needs, then turn it in as their work.



I already wrote the basic programme once, but My hard drive was destroyed, and I didn't want to have to start again. It took me ages last time, and it kinda Knocked the wind out my sails.
Was This Post Helpful? 0
  • +
  • -

#4 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1397
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Genetic Algorithms

Posted 25 December 2009 - 01:22 PM

Quote

I already wrote the basic programme once, but My hard drive was destroyed, and I didn't want to have to start again.
But you have to, unfortunately. At least you learned your lesson about backups when the consequences aren't that horrible.

Quote

It took me ages last time, and it kinda Knocked the wind out my sails.
But, you got it done. So you can do it again.
Was This Post Helpful? 0
  • +
  • -

#5 spintronic  Icon User is offline

  • D.I.C Head

Reputation: -32
  • View blog
  • Posts: 94
  • Joined: 25-December 09

Re: Genetic Algorithms

Posted 25 December 2009 - 01:29 PM

View PostOler1s, on 25 Dec, 2009 - 12:22 PM, said:

Quote

I already wrote the basic programme once, but My hard drive was destroyed, and I didn't want to have to start again.
But you have to, unfortunately. At least you learned your lesson about backups when the consequences aren't that horrible.

Quote

It took me ages last time, and it kinda Knocked the wind out my sails.
But, you got it done. So you can do it again.


K,

In a few *days* I may need help on brackets, That stumped me last time.

E.G.

2*4-3*7

Is not the same as

2*(4-3)*7
Was This Post Helpful? 0
  • +
  • -

#6 debjit625  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 51
  • View blog
  • Posts: 447
  • Joined: 06-September 08

Re: Genetic Algorithms

Posted 25 December 2009 - 01:41 PM

First of all welcome to DIC
Now for your problem you have to show us a bit of work what you have done or may be its not a code but any Idea that you have to share with us and after that we can help you buddy!

Good Luck and Merry Christmas
Was This Post Helpful? 0
  • +
  • -

#7 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 991
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Genetic Algorithms

Posted 26 December 2009 - 02:24 AM

View Postspintronic, on 25 Dec, 2009 - 12:29 PM, said:

In a few *days* I may need help on brackets, That stumped me last time.

E.G.

2*4-3*7

Is not the same as

2*(4-3)*7


OK you need to learn about "BODMAS"
Have a read here
http://www.mathsisfu...der-bodmas.html
Was This Post Helpful? 0
  • +
  • -

#8 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Genetic Algorithms

Posted 26 December 2009 - 10:19 AM

OK, I have a dumb question.

I don't know too much about "Genetic Algorithms" and have never programmed one... but I have read up on them quite a bit. I have NO idea what this could have to do with mathematical order of operations...

Can someone enlighten me?
Was This Post Helpful? 0
  • +
  • -

#9 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2030
  • View blog
  • Posts: 5,430
  • Joined: 27-December 05

Re: Genetic Algorithms

Posted 26 December 2009 - 11:53 AM

Ouch.

Does DIC need some special html tags to highlight sarcasm? :rolleyes:
Was This Post Helpful? 0
  • +
  • -

#10 Maxicat  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 4
  • Joined: 13-December 09

Re: Genetic Algorithms

Posted 26 December 2009 - 12:05 PM

You can use genetic algorithms to find the parameters that solve the equation. For example, you'll be able to find the x and y that solve 5.5x * ( 4.5y - 3.141) = 43.34 , note that here you already know the solution but you want to know the parameters.

Genetic algorithms will suggest the appropriate x and y to plug into the equation. The next step requires parsing and evaluating the equation with proper bracketing etc. For that you can apply Dijkstra's Shunting Yard algorithm to convert the string to postfix notation which is easy to evaluate programmatically.

Practical Genetic Algorithms is an excellent intro to applying genetic algorithms for algebraic evaluation.
Was This Post Helpful? 1

#11 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 991
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Genetic Algorithms

Posted 27 December 2009 - 04:15 AM

View PostNickDMax, on 26 Dec, 2009 - 09:19 AM, said:

Can someone enlighten me?


Are you challenging spintronic to justify his statement here?

Quote

I may need help on brackets, That stumped me last time.


Does it not seem reasonable to you to presume that spintronic knows whether their original solution did or didn't require calculations involving brackets?

Are you suggesting spintronic is giving deliberately misleading information or is perhaps suffering from a mistaken recollection?

It's hard to tell in what area you are declaring your understanding to be deficient.

If your posting was a little more explicit and lucid then it would be clearer where others should attempt to shed light to guide your path.

This post has been edited by janotte: 27 December 2009 - 04:15 AM

Was This Post Helpful? 0
  • +
  • -

#12 spintronic  Icon User is offline

  • D.I.C Head

Reputation: -32
  • View blog
  • Posts: 94
  • Joined: 25-December 09

Re: Genetic Algorithms

Posted 27 December 2009 - 05:39 AM

View PostMaxicat, on 26 Dec, 2009 - 11:05 AM, said:

You can use genetic algorithms to find the parameters that solve the equation. For example, you'll be able to find the x and y that solve 5.5x * ( 4.5y - 3.141) = 43.34 , note that here you already know the solution but you want to know the parameters.

Genetic algorithms will suggest the appropriate x and y to plug into the equation. The next step requires parsing and evaluating the equation with proper bracketing etc. For that you can apply Dijkstra's Shunting Yard algorithm to convert the string to postfix notation which is easy to evaluate programmatically.

Practical Genetic Algorithms is an excellent intro to applying genetic algorithms for algebraic evaluation.



Thanks, that was really helpful.

Before my drive crashed, I was up to point where the algorithm would find *any* (as in, any of many) equation for a given input.

E.G.

Input = 1677

The algorithm may have found 6 * 7 - 8 + 5 + 39 * 6 * 2 / 2 * 7 = 1 677

Obviously it should be (6 * 7) - 8 + 5 + (((39 * 6 * 2) / 2) * 7) = 1 677
Was This Post Helpful? 0
  • +
  • -

#13 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Genetic Algorithms

Posted 27 December 2009 - 06:30 AM

Yea I didn't mean to sound sarcastic, my knowledge is apparently woefully incomplete. Genetic algorithms have come up on many conversations but never in solving algebraic general equations -- they are not even mentioned once in any of my numerical analysis books. The closest I think I have seen was a discussion on chemical equation balancing.

The wikipedia article a linked is much more the view that I had, searching and optimization algorithms. For example I had a long conversation on how they are used in aerodynamics of control surfaces. I believe they are used for optimizing the design and training of neural networks.

Somehow I have just never run across algebraic manipulation before.

I did say it was probably a dumb question since I have only been introduced to genetic algorithms in the abstract.
Was This Post Helpful? 0
  • +
  • -

#14 Maxicat  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 4
  • Joined: 13-December 09

Re: Genetic Algorithms

Posted 27 December 2009 - 10:54 AM

View Postspintronic, on 27 Dec, 2009 - 04:39 AM, said:

Before my drive crashed, I was up to point where the algorithm would find *any* (as in, any of many) equation for a given input.

E.G.

Input = 1677

The algorithm may have found 6 * 7 - 8 + 5 + 39 * 6 * 2 / 2 * 7 = 1 677

Obviously it should be (6 * 7) - 8 + 5 + (((39 * 6 * 2) / 2) * 7) = 1 677


If this is so open ended then you don't even need genetic algorithms. Just generate a bunch of random numbers, bracket them randomly as you go and find one last number to either multiply by or add or subtract by to get the input. You can still use shunting yard and postfix algorithms for evaluating.

E.g. Let's say your random generating process proceeds as follows:

(6
(6 * 7)
(6 * 7) - 8
(6 * 7) - 8 + 5
(6 * 7) - 8 + 5 + (

etc. until you reach something like:

(6 * 7) - 8 + 5 + ((39 * 6 * 2) / 2)

Note that at every step you decide whether to open a new bracket, or close the old one, or keep opening more and more brackets ((( ... )))) but remember to close as well. The decision at which point to open a new bracket is random of course and when to close it is random too. You just have to make sure that for every open bracket there is a closed one, so keep a counter and if you reach the end of the process and there are not enough closed brackets then append as many closing brackets as you need to satisfy open = close count. This way you generate an equation with brackets built in from the start.

After you are happy with the length of the equation, use shunting yard + postfix to find what this evaluates to: 273

Randomly select one more operation: addition, subtraction, etc.

E.g. if addition then you need 1677 - 273 = 1394 as the last number, so append it at the end:

(6 * 7) - 8 + 5 + ((39 * 6 * 2) / 2) + 1394 = 1677

This is a rather random solution and the problem itself seems rather pointless... but then there doesn't seem to be any requirements on how the equation should look, so.. anything goes. This would be more fun if there was some real life application.

If you really want to use genetic algorithms for the sake of using them you can do this:

1. Decide how many variables you want in your equation, let's say 3.
2. Build a random equation string:

(X1*5 + X2*3) / X3*2 = 1677

3. Now use genetic algorithms to find X1, X2, X3 that satisfy this equation. But all of this becomes rather overkill.

This post has been edited by Maxicat: 27 December 2009 - 11:12 AM

Was This Post Helpful? 0
  • +
  • -

#15 spintronic  Icon User is offline

  • D.I.C Head

Reputation: -32
  • View blog
  • Posts: 94
  • Joined: 25-December 09

Re: Genetic Algorithms

Posted 27 December 2009 - 12:54 PM

View PostMaxicat, on 27 Dec, 2009 - 09:54 AM, said:

View Postspintronic, on 27 Dec, 2009 - 04:39 AM, said:

Before my drive crashed, I was up to point where the algorithm would find *any* (as in, any of many) equation for a given input.

E.G.

Input = 1677

The algorithm may have found 6 * 7 - 8 + 5 + 39 * 6 * 2 / 2 * 7 = 1 677

Obviously it should be (6 * 7) - 8 + 5 + (((39 * 6 * 2) / 2) * 7) = 1 677


If this is so open ended then you don't even need genetic algorithms. Just generate a bunch of random numbers, bracket them randomly as you go and find one last number to either multiply by or add or subtract by to get the input. You can still use shunting yard and postfix algorithms for evaluating.

E.g. Let's say your random generating process proceeds as follows:

(6
(6 * 7)
(6 * 7) - 8
(6 * 7) - 8 + 5
(6 * 7) - 8 + 5 + (

etc. until you reach something like:

(6 * 7) - 8 + 5 + ((39 * 6 * 2) / 2)

Note that at every step you decide whether to open a new bracket, or close the old one, or keep opening more and more brackets ((( ... )))) but remember to close as well. The decision at which point to open a new bracket is random of course and when to close it is random too. You just have to make sure that for every open bracket there is a closed one, so keep a counter and if you reach the end of the process and there are not enough closed brackets then append as many closing brackets as you need to satisfy open = close count. This way you generate an equation with brackets built in from the start.

After you are happy with the length of the equation, use shunting yard + postfix to find what this evaluates to: 273

Randomly select one more operation: addition, subtraction, etc.

E.g. if addition then you need 1677 - 273 = 1394 as the last number, so append it at the end:

(6 * 7) - 8 + 5 + ((39 * 6 * 2) / 2) + 1394 = 1677

This is a rather random solution and the problem itself seems rather pointless... but then there doesn't seem to be any requirements on how the equation should look, so.. anything goes. This would be more fun if there was some real life application.

If you really want to use genetic algorithms for the sake of using them you can do this:

1. Decide how many variables you want in your equation, let's say 3.
2. Build a random equation string:

(X1*5 + X2*3) / X3*2 = 1677

3. Now use genetic algorithms to find X1, X2, X3 that satisfy this equation. But all of this becomes rather overkill.


The way I am doing it, is we start with 3 digits, (0+0+0).

The program then randomly chooses 1 of 11 mutation algorithms.

1) Single point Mutation
2) Single point deletion
3) Single point insertion
4) Duplicate a random part of the string & insert in a random place
5) Delete a random part of the string
6) Frame shift
7) Duplicate entire string
8) Rotation of 2 digits
9) Rotation of random part of the string
10) Mutate bracket positions
11) Mutate bracket number


And there are plenty of real-world applications.

E.G. A.I.

A few months back, this algorithm worked out newtons laws of motion in a single day. after being given the data input, of a pendulum swinging.

http://www.wired.com...09/04/newtonai/

I want to see if it can crack R.S.A

This post has been edited by spintronic: 27 December 2009 - 12:57 PM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2