Genetic Algorithms

I'm wondering what applications Genetic Algorithms could have in improving RepRap.

It shouldn't be too hard to use software-based optimizers that can improve our circuits, designs, etc.

Thoughts?

I doubt software could improve the design any better than 1000's of people making Repraps and tweaking the design as they go. That is really gathering momentum this year. It is like genetic evolution in so much as the best design aspects survive and the things that don't work get dropped but the mutations are not random, they are hopefully intelligent design.

---

[www.hydraraptor.blogspot.com]

I've written genetic algorithms in my day job in years past. The question isn't one of whether they could improve outcomes. They definitely could. The question is more one of who wants to invest the man-hours to apply the method to these particular applications. It's not something I have time for.

---

-------------------------------------------------------

Hell, there are no rules here - we're trying to accomplish something.

Opportunity is missed by most people because it is dressed in overalls and looks like work.

Thomas A. Edison

Plus somebody would have to be a slave to the genetic software, building and testing the variants, unless the software had a brilliant physics simulator in it. As most of the random mutations would be no hope dead ends it would be a lot of work, most of it pointless.

---

[www.hydraraptor.blogspot.com]

>
>unless the software had a brilliant physics simulator in it.
>
Yeah, I should have mentioned that bit. Unless you have an evaluation function, you can't have genetic algorithms. I don't think that we have any that can be reduced to pseudocode.

---

-------------------------------------------------------

Hell, there are no rules here - we're trying to accomplish something.

Opportunity is missed by most people because it is dressed in overalls and looks like work.

Thomas A. Edison

There are some brilliant physics simulators available...
For example [www.bulletphysics.com] (C++ & Java)
Or [www.ode.org] (C++)

However, it doesn't solve the evaluation function problem...


---
[www.coded.be]

They might be brilliant but I would be very surprised if you could input a 3D model including its materials and simulate the extruder building an object, predicting all the defects like stringing and warping and working out how long it would take for things to wear out. Sounds like science fiction to me.

---

[www.hydraraptor.blogspot.com]

There have been some very science fictiony things done with genetic algorithms. I've done one or two. I fear, though, that the app proposed here is simply too fuzzily defined to yield useful results.

---

-------------------------------------------------------

Hell, there are no rules here - we're trying to accomplish something.

Opportunity is missed by most people because it is dressed in overalls and looks like work.

Thomas A. Edison

I'd be interested in hearing about your experiences with GA, Forrest. Unfortunately, it probably isn't related enough to reprap to post here. Got any better ideas?

On a more topic related note: Yes, the extruder physics stuff would be hard to do with GA, but the suggestion about circuit boards would be more approachable.

Maybe you could use it to come up with a better slicing/filling algorithm for the software, or use GA to design better corner brackets that use less material, but are just as strong. That should be possible to simulate without a fancy filament warping function.

Do you think any of those physics sims could tell us how far apart our fill threads can be without sagging too much? Saving on material and build time is certainly a worthy goal, even without achieving higher accuracy in model shape.

Hi Forrest,

actual working GA-samples would be interesting for me too.

20 years ago i made some 'traveling salesmen'-optimisation with a neural-network-chain for CNC-drilling PCB's on my Atari-ST and hoped to develop a 'self-trained' perfect 3D-CNC-controller, but then my diploma examinations went hot and i somehow lost contact ...

Viktor

I doubt that my GA samples would be of much use to the effort contemplated. The major effort I undertook was to simulate heritable IQ drift over several centuries in traditionalRussian Jewish Shtetl and Nguni kraals.

---

-------------------------------------------------------

Hell, there are no rules here - we're trying to accomplish something.

Opportunity is missed by most people because it is dressed in overalls and looks like work.

Thomas A. Edison

... aiii

By the way ... could you prove true the effect of IQ-multiplying when two long time separated genetic lines recombine?

Viktor

VDX Wrote:
-------------------------------------------------------
> ... aiii
>
> By the way ... could you prove true the effect of
> IQ-multiplying when two long time separated
> genetic lines recombine?
>
I'd need a clearer statement of the proposition that I think that you are making. Got any prior art or links you can point me at?

---

-------------------------------------------------------

Hell, there are no rules here - we're trying to accomplish something.

Opportunity is missed by most people because it is dressed in overalls and looks like work.

Thomas A. Edison

Hi Forrest,

... no links ... i read this somewhere and was interested if it's true that crossbreeded animals (or people too) between long time separated genetic lines are significantly shrewder than their parents

Viktor

Your thinking of hybrid vigour [en.wikipedia.org] . However it's not really applicable here since it's most evident when the parents are highly inbred, usually in artifical selection cases where people have been inbreeding the plants/animals for years. I doubt any of the RepRap stuff qualifies and in any case, to work you'd need to actually have some sort of genetic algorythm at work in the background which we don't. Taking the best features from each model out there is not the same thing (even if it may be a good strategy.)

Also whether it has any real application to humans is also quite controversial. Sure if you're talking about highly inbred populations outbreeding has clear advantages but it may not make so much difference with humans since despite what the KKK et al want us to believe humans are actually a (mostly) incredibly mixed population.

Edited 1 time(s). Last edit at 01/13/2009 11:09AM by Nil Einne.

With generational genetic drift in a more or less homogeneous population you have some fairly well-understood statistical mechanisms. The most usual one you see says that the IQ of children of a couple will fall within a fairly narrow distribution curve the mean of which can be taken to be the average of the parents' respective IQ's.

I modeled two situations, the first was a Jewish Shtetl in which bright males were identified quite early in life and encouraged to undertake rabbinic studies. Socially, such males, on completing their studies were considered prized marriage material by the Shtetl and pretty much had their pick of eligible young women. The rabbi's family was also expected to be large and the children thereof were similarly considered to be prized marriage material.

The question that I posed was one of accepting this social mechanism for encouraging bright males to have large families who were married back into the community, how long would it take for the mean IQ of the Stetl to exhibit the 10 point IQ advantage that Jewish populations consistently show over other european populations. The answer came out to about 250 years. I ran about a dozen variations on the scenario and found that the time frame only deviated from 250 years by about +/-20 to 30 years.

Against that I modeled a the marriage and child rearing customs common in southern African Nguni kraal where families accumulate capital over generations and the family patriarch is able to purchase multiple wives which aid him in capital accumulation. My genetic models of that mechanism typically showed an extremely gentle downward drift of population IQ. The drift that I detected was so small that I wouldn't vouch for it even existing. The IQ drift for Jewish Shtetl, however, was very pronounced and much stronger than I would have guessed before the modeling exercise.

The problem with the crossbreeding, as it were, of human populations with respect to IQ is that most of the information that we have comes from the 20th century. During that period the Flynn Effect complicates separating out IQ drift resulting from other factors.

Someday, if I am spared for long enough, I hope to revisit that exploration and maybe get a handle on why the Flynn Effect set off the massive upwards IQ drift that it did in the 20th century in the industrialised world. Knowing the hows and whys of the Flynn Effect would be VERY interesting.

---

-------------------------------------------------------

Hell, there are no rules here - we're trying to accomplish something.

Opportunity is missed by most people because it is dressed in overalls and looks like work.

Thomas A. Edison

Nil Einne Wrote:
-------------------------------------------------------
>
> Also whether it has any real application to humans
> is also quite controversial. Sure if you're
> talking about highly inbred populations
> outbreeding has clear advantages but it may not
> make so much difference with humans since despite
> what the KKK et al want us to believe humans are
> actually a (mostly) incredibly mixed population.
>
DNA surveys consistently indicate that genetic variation amongst humans not originating from subSaharan Africa is extremely slight, less by several magnitudes for all five billion of us than what you'd encounter in the average Chimpanzee troop.

Not to put too fine a point on it, we're (the Euroasians amongst us, that is) are as inbred as a bunch of rough collies. That could go a long way towards explaining the average 30 point difference between Euroasian and subsaharan African populations. Genetically, subSaharan Africans are humanity's root stock, to use a good horticultural term. Most of humanity's DNA variation is found amongst those who never left Africa. We should guard that treasure house of DNA very carefully. You never know when we might really, really need it.

---

-------------------------------------------------------

Hell, there are no rules here - we're trying to accomplish something.

Opportunity is missed by most people because it is dressed in overalls and looks like work.

Thomas A. Edison

Forrest Higgs Wrote:
-------------------------------------------------------
> DNA surveys consistently indicate that genetic
> variation amongst humans not originating from
> subSaharan Africa is extremely slight, less by
> several magnitudes for all five billion of us than
> what you'd encounter in the average Chimpanzee
> troop.

But that's precisely my point. Given the low variation and the fact that what variation does exist has been shown to be not strongly linked to the concept of race, it doesn't make sense that hybrid vigiour would be observed. The simple fact is, as much as certain groups would like to claim otherwise, there is no such thing (generally speaking) as all these pure races that shouldn't mix. In fact, most of what we think as races don't really exist on a genetic level. So it's unlikely your going to get hybrid vigour and mixing or not doesn't really matter since by and large, humans are already mixed.


> Not to put too fine a point on it, we're (the
> Euroasians amongst us, that is) are as inbred as a
> bunch of rough collies. That could go a long way
> towards explaining the average 30 point difference
> between Euroasian and subsaharan African
> populations. Genetically, subSaharan Africans are
> humanity's root stock, to use a good horticultural
> term. Most of humanity's DNA variation is found
> amongst those who never left Africa. We should
> guard that treasure house of DNA very carefully.
> You never know when we might really, really need
> it.

Forrest Higgs Wrote:
-------------------------------------------------------
> With generational genetic drift in a more or less
> homogeneous population you have some fairly
> well-understood statistical mechanisms. The most
> usual one you see says that the IQ of children of
> a couple will fall within a fairly narrow
> distribution curve the mean of which can be taken
> to be the average of the parents' respective
> IQ's.
>
> I modeled two situations, the first was a Jewish
> Shtetl in which bright males were identified quite
> early in life and encouraged to undertake rabbinic
> studies. Socially, such males, on completing
> their studies were considered prized marriage
> material by the Shtetl and pretty much had their
> pick of eligible young women. The rabbi's family
> was also expected to be large and the children
> thereof were similarly considered to be prized
> marriage material.
>
> The question that I posed was one of accepting
> this social mechanism for encouraging bright males
> to have large families who were married back into
> the community, how long would it take for the mean
> IQ of the Stetl to exhibit the 10 point IQ
> advantage that Jewish populations consistently
> show over other european populations. The answer
> came out to about 250 years. I ran about a dozen
> variations on the scenario and found that the time
> frame only deviated from 250 years by about +/-20
> to 30 years.

I would like to know how you came out with those figures. The genetic basis for IQ is rather poorly understood. There is definitely an inherited component but how large it is remains an open question. Even if it's true "IQ of children of a couple will fall within a fairly narrow distribution curve the mean of which can be taken to be the average of the parents' respective IQ's" which I'm somewhat doubtful (most studies I've seen suggest the correlation with parental IQ is far from clear) this doesn't prove a genetic basis since amongst other things contrary to what some people claim, IQ isn't purely inate. Of course, if the correlation is there, it's possible/likely? it would increase whatever the cause but I would suggest that's far from certain.

For that matter, IQ is poorly understood. All it actually measures is your ability to do IQ tests. There appears to be some correlation with what we call 'intelligence' but it's at best only a loose one.

Also it doesn't sound to me like you study considered the IQ of the female partner. The fact that the male had the pick doesn't mean they choose the ones with the higher IQ. It's easily possible to imagine that they choose the ones with the IQ 10 points lower on average therefore likely cancelling out any advantage their higher IQ had presuming your theory of IQs holds true. Also, even though their children could may have been high up in the social scale, having large families means you can afford to devote less attention/resources to the children you have. For humans, having large families is not necessarily the most effective evolutionary strategy. It could easily lead to a lower IQ of the children and a lower chance of evolutionary success of the children which the social (and genetic?) advantage they have due to their parents may not be enough to make up for.

Indeed there are other factors to consider. Just because the parents are encouraged to have more children doesn't mean they do or are able to. It may be that the high IQ is correlated with other factors which reduce evolutionary success. For example, if the Father is more likely to die young. Or for that matter beyond having more children is less able to raise the children effectively. Indeed even social factors could come into play. Does the increase pressure on the father to perform according to societal expectations lead to a lower median age at death or negatively effect the way they raise their children?

Bringing the female into it again, regardless of the fact the father has the pick of the crop or the IQ of the female they select, there's no guarantee they will select the most evolutionarily successful females. Given the societal factors at play, it's possible that the females they pick are not the best choice. Perhaps for example, the females are more prone to infidelity (whose effect is going to be even more difficult to quantify) or has similar problems to those I raise for the father.

Of course sexual selection will likely come into play. The fact that they choose the females and they had the pick of the crop means that whatever the traits they must be those considered most important amongst their community and therefore whatever inherited component of these traits that's passed to the children would give them an advantage even if they paradoxically also give them a disadvantage. (The same of course for the father.) This of course plays back into the societal edge the children have. But again, rather extra fitness component they have must be weighed against any negative effect on fitness it may also have.

BTW, I would avoid the term 'drift' when talking about evolution. Drift usually refers to genetic drift which is random and doesn't seem to be what you're referring to. It does have to be considered in any calculation of evolutionary rates though.

P.S. A bit tired so apologise if any of that didn't make sense. I think I covered the basics though. Since this is OT and not really something of great interest to me, I'll probably stop there. I have some background in biology so know calculating evolutionary rates is an extremely complicated thing. And working out how a trait will change in a certain situation even more so given the near infinite number of variables many of which can have a fairly large effect. Particularly in a beast as complicated as humans. If you haven't already, I suggest you consult an evolutionary biologist (which I'm guessing your not) preferbly one with a background in statistics/biometry who could advise you further on your calculations. I think you may not have quite understood the complexity of the calculations.
P.P.S. In case I was wrong about how far you went, were any of those calculations published in a peer-reviewed journal?

Edited 2 time(s). Last edit at 01/13/2009 04:21PM by Nil Einne.

... now, that's the real spirit

I found some similarities with breeding pets, cultural/social relationships between long time separated folks (eg. eastern and western europeans after breakdown of the Sowjet Union) and developing repraps/repstraps with different strategies ...

Maybe there are some significant patterns we can use for faster 'rep-volution'?

Viktor

Nil Einne Wrote:
-------------------------------------------------------
>
> There is definitely an inherited component but how large it is remains an
> open question.
>

Mostly it's a politically explosive question the possible answers to which fly in the face of a half-century of social orthodoxy.

Thank you for your review of the genetic programming project I undertook.

I mentioned the content of what I did mostly in reply to Viktor's query, not from any desire to spark a debate about IQ or the vexed IQ vs race question. After I got my PhD in 1990 I undertook a number of explorations using various techniques mostly to satisfy my own curiosity and relax. This was one of them. One of the others was slowly, painfully working my way through the proofs of Kurt G

Edited 1 time(s). Last edit at 01/13/2009 05:30PM by Forrest Higgs.

---

-------------------------------------------------------

Hell, there are no rules here - we're trying to accomplish something.

Opportunity is missed by most people because it is dressed in overalls and looks like work.

Thomas A. Edison

Fascinating.

How were G

I used the old Nagel and Newman explication of G

Edited 1 time(s). Last edit at 01/13/2009 11:41PM by Forrest Higgs.

---

-------------------------------------------------------

Hell, there are no rules here - we're trying to accomplish something.

Opportunity is missed by most people because it is dressed in overalls and looks like work.

Thomas A. Edison

Hi,

On the topic of applying GA (or, more generally, self-learning iterative algorithms) to reprap, my suggestion is that is might be more feasible than you think. You don

Colecoman: The problem with that approach is that it presumes a very high rate of interactive dataflow between the PC and the reprap machine. That's not happening at the present time. Right now, reprap machines are either stand alone or more or less peripherals to your PC.

---

-------------------------------------------------------

Hell, there are no rules here - we're trying to accomplish something.

Opportunity is missed by most people because it is dressed in overalls and looks like work.

Thomas A. Edison

I really love the camera idea. Though, scanning may not require anything as complex as a camera. A camera might bring the cost up too much. A simple light detector or laser of some sort may do the trick.

As for data flow, it shouldn't be too hard to hack together a bunch of open source monitoring devices to record data like temperature, speed, vibration, etc. I think that would be a very constructive thing to do.

Hm, I don't look forward to trying to code up a vision system from scratch....

but, an accelerometer on the write head might be useful. Keep an eye on the RMS power of the vibration the head experiences; that might be able to detect the next time I have an all-night long series of head collisions due to a bad programming job.

A strain gauge on the extruder mount would do that as well, and it could do a few other things as well, like finding the bed height automatically. Could take some time though.

Wade

Wade Wrote:
-------------------------------------------------------
> but, an accelerometer on the write head might be
> useful. Keep an eye on the RMS power of the
> vibration the head experiences; that might be able
> to detect the next time I have an all-night long
> series of head collisions due to a bad programming
> job.

Why dont you get a shock absorber? Foam works pretty well for this kind of problems

The accelerometer wont be very useful if you have lots of vibration because when you want to fill a gap quickly, the "vibrations" will shut the machine off. Try to look at [forums.parallax.com] from parallax, there is shown how their X-Y accelerator works.


Also thinking about the strain gauge... You could also use it to calibrate the Z-axis, but its also possible with IR or ultrasonic sensors... Or in the case of "money is not a problem" a webcam?

Edited 2 time(s). Last edit at 01/14/2009 05:15PM by Mr. Seeker.

Well, I figured that the rms power of the vibration will be much higher for stuck head situation, where the stepper is jumping steps at high speed. It's certainly noisy as hell when it happens! Should be easy to set a limit that will pass a zig zag path, but fail multiple head collisions. A single head collision would be more difficult to detect without a strain gauge.

I prefer the Analog Devices ADXL series, but I haven't used them for a few years. Even so, my webcam only cost me $10 new; I'd be hard pressed to put together an accelerometer monitoring system for less than that. Still, it could be fun.

I wonder, does anyone make a sort of instrumented bolt for a reasonable price? The extruder mount could use a pair of bolts with strain gauges, and you could watch the change in bolt tension when you run into something. Probably cost as much as the RepRap.

Wade

edit - the neat thing about strain gauge vs optical measurements is that the strain gauge will tell you how much your extruder has elongated due to heating, warping, or in my special case, catastrophic failure.

Edited 1 time(s). Last edit at 01/14/2009 05:31PM by Wade Bortz.

... the camera could do a better scanning job when treating with photogrammetry - take two picrures from different positions and calculate the displacement of some relevant edges or previous placed colour-dots ...

Even GA or NeuralNetwork-simulation could help a lot - i knew someone who built high-speed-3D-scanners with two cameras that acts like the human brain with image-recognition ... extremely fast, super precise but extremely expensive too

Maybe an open source approach and some clever people can do the same?

Viktor