"Evolved" Caches Could Speed the Net

SpaceDilbert writes "According to New Scientist, evolutionary algorithms could make many network caches twice as efficient. This article describes a study carried out by a US researcher and two German academics, who "evolved" algorithms to determine what data should be held at a cache and for how long."

Caching

[Zorilla]

According to New Scientist, evolutionary algorithms could make many network caches twice as efficient.

That's easy, just cache 4 boobs at a time instead of two

Re:Caching

[Anonymous Coward]

Wouldn't it more efficient to cache 1 boob and display it x times? Sort of a boob pooling.

Algorithms

[th1ckasabr1ck]

Pablo Funes of US company Icosystem and Jürgen Branke and Frederik Theil of the University of Karlsruhe in Germany used "genetic algorithms", which mimic Darwinian evolution, to develop strategies for internet servers to use when caching data.

It would be interesting to see exactly which algorithms they are talking about here. I wouldn't be surprised if they drew some ideas from garbage collection algorithms also.

Re:Algorithms

[spektr]

I wouldn't be surprised if they drew some ideas from garbage collection algorithms also.

I suppose you're the clever garbage man from the Dilbert cartoons. Because as an engineer I don't really get the connection between garbage collection and caching algorithms. Now that we have covered the first two frames of the cartoon - what's in the third frame where the garbage man makes me feel ashamed by explaining some complicated concept of engineering?

Re:Algorithms

[ahem]

...as an engineer I don't really get the connection between garbage collection and caching algorithms. ...

It seems to make sense to me, if only because the two are complimentary problems. Caching is figuring out what stuff is valuable so you keep it around. GC is figuring out what stuff is valuable so you can throw away the rest. Kind of like in probability where it's easier to figure out the likelihood of something not happening and then subtracting from 1 to figure out how likely it is to happen.

Re:Algorithms

[ezzzD55J]

Humbug, the big difference is: in GC there's perfect knowledge about what you want to throw away (unreferenced or only circularly referenced objects), and the problem is how to find out efficiently.. In caching the whole problem is to figure out which objects to keep, and beyond that, efficiency is no problem.

not even close

[Anonymous Coward]

Garbage collection is required to be correct, but is allowed to keep extra stuff around as memory permits. Everything that must be kept can be calculated deterministically without future knowledge, and the same holds true for everything that can be discarded. Approximation merely allows the what can be discarded calculation to progress faster. In garbage collection it is not correct to throw out something that will not be used in the future unless it is also unreachable.

For cacheing there is no requirement of correctness. Performance is improved when things that will be used in the future are kept. There is no correctness requirement for keeping things around, and indeed best performance often requires discarding things that will be used in the future. In addition, there is no way of determining what will be used in the future without knowledge of the future. The correctness requirements of a cache are related to security (don't cache sensitive information) and staleness (don't cache stuff that is too old), but even those may be relaxed rather than strict requirements.

Fundamentally the two problems are very different, and algorithms that deal are successful in the two different cases will likely be very different.

Re:not even close

[Alexis de Torquemada]

In garbage collection it is not correct to throw out something that will not be used in the future unless it is also unreachable.

It is correct to do so, but in practice, you cannot be certain that the data will not be used, unless it's unreachable.

Re:Algorithms

[gr8_phk]

"GC is figuring out what stuff is valuable so you can throw away the rest."

I thought Garbage Collection was shuffling stuff around with the goal of consolidating all the stuff you don't want into large blocks (collecting the garbage) so the space can be reallocated efficiently.

The smart garbage man is on vacation.

Re:Algorithms

[spitzak]

You seem to have the terms confused. GC refers to algorithims where you know for a fact that some data is not needed ever again. Caching refers to algorithims where you *might* need the data again, but you can also recreate it if it is thrown away. Many programs will do this with their own memory and data structures, and certainly the algorithims used there are relevant to this, but it is still called "caching", not GC.

Re:Algorithms

[aiyo]

GC and caching are done very differently. In java memory has a counter associated with it. When you have two pointers to that memory then it has the value 2 stored somewhere with the memory. When you change the reference the counter is decremented. Every once in a while the GC will come along and free memory with a counter of 0. If you dereference that memory so that you have absolutely no pointers anywhere using the memory then you will have lost that memory although it is not freed until later.

Re:Algorithms

[arth1]

It would be interesting to see exactly which algorithms they are talking about here. I wouldn't be surprised if they drew some ideas from garbage collection algorithms also.

I'm not sure how relevant that would be, as garbage collection in general is way more radical than what a cache needs -- a cache operates best when full.

The best algorithm for improving a cache is, of course, to increase the size of the cache. :-)

Regards,
--
*Art

Re:Algorithms

[Surt]

Sometimes increasing the cache size without adjusting the algorithm reduces performance.

Re:Algorithms

[laudney]

Garbage collection problems are far easier than caching problems in networks. There are many reasons. The most important one is that in garbage collection, 'references' are basically 'pointers'. An object that's not pointed to by any other objects is considered garbage. And don't forget, in garbage collection, you can even 'stop the world'!

By contrast, in caching, 'references' are 'client requests', which are unpredictable and highly variable. Furthermore, on busy networks, there is seldom a moment for you to 'stop the world' and 'evolve' for a while!

In the story, people use network simulators and randomly generated requests. Since network simulators are notoriously simplistic and inaccurate, and caching is heavily influenced by real-life workloads, I'm interested to know whether their algorithm is applicable in reality.

What makes a good cache?

[YankeeInExile]

Well, I have found one flaw in the methodology:

The starting population of algorithms was tested on the simulator using randomly generated requests.

I would think this would breed out of the caching system any affinity to locality-of-reference.

One of the things I did each morning when I was running a cybercafé was "prime" the Squid cache by running a little script that did a wget -p on all of the URLs in the portal page, and a few sites that were not. And it definitely did improve performance for most users.

One of my unrealized dreams would be some sort of speculative-fetch algorithm for Squid that would basically do a breadth-first fetch on a page while the user was busy reading it.

Of course in my not-so-humble opinion, the biggest problem with any caching system is the population of websites that, through either malice or incompetence develop content that is cache-hostile, and call it "experience enhanced".

Re:What makes a good cache?

[Short Circuit]

What you get out of the breeder shouldn't be what you put into production.

Assuming you can still read the code, you're still going to want to put in common-sense improvements that the GA's didn't discover.

Re:What makes a good cache?

[YankeeInExile]

So, do you posit that the purpose of the GA is just to give human programmers insight into avenues they might not have otherwise considered?

Re:What makes a good cache?

[AKAImBatman]

I'm actually a bit surprised that neural nets haven't yet entered common usage. In theory, such a net would be far more "intelligent" (sort of) in making decisions.

e.g. This page looks a lot like a truly dynamic page, so let's not cache it. Over here, this is dynamic, but only slightly so. Let's cache it and index the most likely path the user will take.

Have CS researchers given up on the neural net approach, or are the nets still far too unstable for real world use?

Re:What makes a good cache?

[Short Circuit]

I actually wrote a paper on those in middle school. The problem with them is that the larger ones are very difficult to tune.

It turns out that if you have more than three layers (in other words, if you have any layers between the input and putput), you run into proplems in training when the network doesn't work as well as you want it to perform, but furthur cycles of your training algorithm don't seem to make it any better.

The comp.ai.neural-nets FAQ [fu-berlin.de] was my primary source for that paper. Read that if yo

Re:What makes a good cache?

[a_ghostwheel]

There are other types of neural networks than just standard back-propagating ones. Linear vector quantization is much better at solving classification problems (ART-based algorithm should be good too). Problem is that in many "on-the-surface" problems have better specialized solution than just a generic NN or GA brute-force approach. This situation led to drastic decrease in funding for NN research.

Re:What makes a good cache?

[autophile]

Have CS researchers given up on the neural net approach, or are the nets still far too unstable for real world use?

Well, no, it's just that neural nets have to use a carefully calculated and parameterized error-propagating algorithm, as well as an appropriate architecture and size of network, and if you choose the wrong one, you're basically hosed. Genetic algorithms (and genetic programming) have learning algorithms that are much simpler to understand and implement -- even though there's a lot of argumen

Re:What makes a good cache?

[Elwood P Dowd]

Your existing responses are a little more complex than your question.

The reason that neural nets are not in common usage is because they must be specifically designed for the problem they are going to solve. That design work is difficult & requires expertise. Neural nets are not suited to every type of problem. But no, CS researchers have not given up on neural nets.

Re:What makes a good cache?

[kerrbear]

What you get out of the breeder shouldn't be what you put into production. Assuming you can still read the code, you're still going to want to put in common-sense improvements that the GA's didn't discover.

Could this be the long awaited answer to harmonizing Creation and Evolution :-)

This seems a little...selfish

[PhysicsGenius]

"Priming the cache" and "doing a breadth-first fetch on a page" are both things that create *more* network traffic on the off-chance that it might save some number of microseconds for the user. It's basically a Tragedy of the Commons situation. Everyone would be better off if no one pre-fetched links, but any given person is better off if they don't cooperate with that global model. So everyone just grabs what they can get and everyone is worse off.

Re:This seems a little...selfish

[droleary]

"Priming the cache" and "doing a breadth-first fetch on a page" are both things that create *more* network traffic on the off-chance that it might save some number of microseconds for the user.

More traffic isn't necessarily bad. While what you say is true, you fail to note that user-initiated traffic is done in bursts. Just like your CPU is idle >95% of the time, so is your network connection. So all users benefit, both in real and perceived performance, when there is a steady 100% utilization.

So everyone just grabs what they can get and everyone is worse off.

Again true, but naive. What would be better is if there were a mechanism to prioritize the pre-fetch cache. Every page has one link that is pretty much the most likely next page. Then a secondary link, and so on. Ideally, a site owner should be able to put that priority list somewhere in the page such that a user agent can start getting it after the current page has loaded and is being read. Otherwise, maybe the user agent can favor new content (i.e., compare this load of Slashdot with the one done five minutes ago and grab the links in the diff). That's a far cry from a mad grab, and would probably benefit all parties involved.

Re:This seems a little...selfish

[qbwiz]

There's the link tag for html headers, which specifies the next page, previous page, and things like that. It's not prioritized, but if it's used, it can give a good idea of what the user will do.

Re:This seems a little...selfish

[droleary]

There's the link tag for html headers, which specifies the next page, previous page, and things like that.

Ah, I knew it was too good an idea to be all my own! For those not aware of how to use the link element for that, I found this page [w3.org] as well as this one [w3.org]. I don't know how widely it is used by site designers, and I can't say I know of any web browsers that use it, but I would say it is definitely something a proxy server should be taking advantage of. It's use is even stated directly in the second

Re:What makes a good cache?

[Dachannien]

Not a flaw. When dealing w/ GAs, one needs to create the initial generation somehow, and using 'randomly generated' GAs provides a good start that is statistically unlikely to be biased or stuck in a local maxima/minima.

Except that wasn't what the poster was getting at - he was noting that the trials provided to the GA were essentially random, and didn't necessarily reflect what the cache is likely to see IRL.

I suspect, however, that this is an error in the NS article, and that the data sets *were* tuned

Ok..

[Killjoy_NL]

"An important consideration is what incentives there are for caching information for other users."

So the ISP's will have to upgrade their soft/hardware to make this work?
Will that be worth it ?

In my opinion the article was a bit light on details :(

Re:Ok..

[jarich]

Wouldn't this lessen the bandwidth requirements for an ISP? By caching files locally, your local ISP could host more users with less bandwidth.

Sounds like it could save an ISP a ~lot~ of money.

Algorithms

[bchernicoff]

I wonder if they evolved logic to counter the slashdot effect. 1. Scan slashdot.org for new stories every five minute. 2. Scan new story for links. 3. Cash those pages.

Re:Algorithms

[bunyip]

I wonder if they evolved logic to counter the slashdot effect. 1. Scan slashdot.org for new stories every five minute. 2. Scan new story for links. 3. Cache those pages.

That would be the "suicide algorithm". As the server goes up in flames from the Slashdot-effect it brought upon itself, it would become the first cyber recipient of a Darwin Award.

Alan.

Business model

[dk.r*nger]

1. Scan slashdot.org for new stories every five minute.
2. Scan new story for links.
3. Cash[sic] those pages.

4. PROFIT!

what about worm traffic?

[garcia]

From what I can tell a good majority of the traffic that my machine receives is worm traffic. Would these genetic routines be setup to disregard those as cache data? If that's the case would they be setup to just block that data?

That alone would save me quite a bit of traffic as people on my subnet hit me constantly with their infected machines.

66.41.161.120 hit my machine 57 different times (that isn't individual requests, that's total times).

Re:what about worm traffic?

[JJahn]

66.41.161.120! Those bastards keep showing up on my logs too. I think I'm going to DoS them right no........CARRIER LOST%@&&!_!$_!

LRU Rules

[Mirk]

There's a good reason why LRU caching (least recently used) is so widespread, and that is that it's very very hard to come up with a sophisticated algorithm that outperforms this very naive one.

For the uninitiated, elements are added to an LRU cache until it fills up; thereafter, whenever a new element is added, space is made for it by throwing away the least-recently used one. Note, least recently used, not the least recently added, i.e. the oldest, since an element that was cached long ago may be used all the time, and so be well worth its place in the cache. For example, consider the company-logo image that your browser caches when you visit a new site and that is embedded in every page on that site. However old it gets, it's likely to continue to be used while you're on the site. As soon as you move to another site, it gradually shuffles its way down the deck until it falls off the bottom - which is precisely what you want.

Re:LRU Rules

[rossjudson]

ARC caches fairly handily outperform LRU. When LRU is appropriate they adapt towards it. When frequency is important they adapt towards that.

Re:LRU Rules

[Fzz]

ARC caches fairly handily outperform LRU.

Thanks for the pointer. Here's a link to some background [ibm.com] on ARC, and a paper [ibm.com] describing the algorithm. Looks like an interesting algorithm.

Re:LRU Rules

[arth1]

There's a good reason why LRU caching (least recently used) is so widespread, and that is that it's very very hard to come up with a sophisticated algorithm that outperforms this very naive one.

For small cache sizes with one or a few fairly similar users, this is true. For larger cache sizes with a large number of users, it's almost always better to expire based on both LRU (Least Recently Used) and LFR (Least Frequently Requested). You may want to cache all those sucky Christmas links until next year

Not DNS

[artlu]

It already takes forever for DNS changes to propagate through every network, which can be extremely frustrating when you have a high bandwidth domain. There definitely needs some optimization on the DNS front.

GroupShares Inc. [groupshares.com]

Re:Not DNS

[Short Circuit]

If I'm not mistaken, the DNS RFC takes into account the fact that domain records will be cached. That's why the records have expiration and refresh times on them.

Re:Not DNS

[Feyr]

except when your zones get around to morons ISP that force your zones to have a higher TTL than you specified, which unfortunately here is being done by the big player

Re:Not DNS

[YankeeInExile]

It already takes forever for DNS changes to propagate through every network, which can be extremely frustrating when you have a high bandwidth domain. There definitely needs some optimization on the DNS front.

If your zones are taking too long to propogate, maybe you need to Read The Fine Manual [isc.org] ... especially the parts around Refresh and Time to Live

Great

[CptChipJew]

So now Slashdot is going to get cached for a long time and I'll never get first post again :(

bittorrent tie in?

[Chuck Bucket]

I"ve always wondered if something along the lines of cache complimented with a Bittorrent type of scheme couldn't help speed up the internet. that way bits would be mirrored all over, and a server could pull them in faster since more servers did less work each.

just something I'm thinking about today, well, that and the Kerry/Edwards pairing.

PCBRwer342$#

Re:bittorrent tie in?

[hackstraw]

I've been wondering this as well. I think it would be cool for all of the internet/browsers to like a big p2p setup. Where the originial webserver is the canonical source for info, and it keeps history of its visitors with ways to figure out the best "route" or network neighbor.

However, in practice, I'm not sure how useful somehting like this would be. Most websites today have so much dynamic info, that it simply would not work. For example, /. would only be able to cache its graphics.

This would be c

Re:bittorrent tie in?

[Chuck Bucket]

Yes, so there's be a dameon on servers that could be a beacon to others, and only have it catalog certain directories that contained 'static' content that didn't change very often. then the main server would only be required to generate the dynamic content, whilest the static would be provided by others.

I'm thinking of almost a distcc way of handling this, where the server can dole out tasks to any/many other servers that it finds that are 'willing' to help out.

PCB%$s

Re:bittorrent tie in?

[Kopretinka]

I understand the parent suggestion as a dynamic list of current mirrors at every site (or page).

IMO peer-to-peer caching/mirroring would work for big chunks of data where the overhead of finding a cache (guesstimate a few to a few tens of round-trips among peers and the original site) would be insignificant compared to the actual download time. For short pages it would be better just to return the page as opposed to the current list of mirrors.

On the other hand if the page contained (in the HTTP metadat

Next Gen Networking?

[arieswind]

From the article:
He[Pablo Funes] suggests networks might in the future be designed to work out who deserves the most help for themselves. "Sophisticated network behaviours might implement rules for reciprocity and trust," he says. "And conversely, for not cooperating with other others who try to abuse our resources."

The future of network security? Imagine the next computer virus outbreak: Every network in the world could recognize the virus type activity and allocate them lesser or zero resources, maybe sending them a "Virus detected, please run antivirus software or contact your IT Department" notice, and detecting outside attacks from viruses and automatically flagging them as unsafe, and not give much(or any) attention to traffic from or to that site

Re:Next Gen Networking?

[danharan]

Every network in the world could recognize the virus type activity and allocate them lesser or zero resources, maybe sending them a "Virus detected, please run antivirus software or contact your IT Department" notice

Could also work if it communicated "$IP being DDOSed, please trace back and isolate those who are doing this"?

Basically, I think we really should be thinking about how to build an immune system for a network and what minimal behaviour from the nodes would achieve it.

Evolutionary Computing

[snowlick]

Stuff like this is what keeps computing interesting, I think. This technique can be used by almost every business in a situation in which optimization might be necessary. I assume that covers most tasks someone would want to accomplish. By utilizing these algorithms to explore search spaces previously thought to be too large I predict we'll experience some pretty explosive advances in the near future in areas from farming to software development. But that's kind of obvious.

the details of their method

[Dezer]

Actually, I do genetic algorithm / genetic programming research at the university of michigan. It's unlikely that these guys are using genetic algorithms to develop a new algorithm, but are rather using an existing algorithm and *tuning* the associated parameters using a GA. Given a list of parameters, GA's work by finding the best combination of parameters. As a result, the settings could be constantly tweaked (say on a daily/hourly basis) and different servers could still have different regional settings. My only problem with the concept is that it still depends on the tuning of pre-existing algorithms... but still - the results they share (2x improvement) is encouraging.

Re:the details of their method

[NoOneInParticular]

You seem to have missed out on Gecco in Seattle this year, where the guys in the article presented their paper. They nearly got the first prize in the GP track, but were beating by some researchers doing quantum programming using GP. What it boils down is that they evolved the priority function that was used in caching, i.e., the thing that makes the caching tick. So it was not a parameter optimization method they used, but a true induction of a priority function.

Al Gore is a great contributor

[hugesmile]

evolutionary algorithms could make many network caches twice as efficient

Once again, Al Gore has his hand in the shaping of the internet.

I'm sure everyone in the Slashdot community will miss him - even if you didn't enjoy his work, there's no denying his contributions to popular culture. Truly an American icon.

A note on hill-climbing

[Animats]

Genetic algorithms are methods for optimization in bumpy spaces. The basic goal is "find x such that f(x) is maximized". As optimization algorithms, they should always be tested against the two simple optimization algorithms - basic hill climbing, and random search.

If the search space is not dominated by local maxima, basic hill climbing (go for the best neighboring value) will work. And it will be fast. If the function is differentiable, it can be orders of magnitude faster than other methods, because you can use a variant of Newton's Method.

If the search space is small, random search (just guessing) will work by exhaustively searching the space. This is obvious, but tends to be ignored in academic papers all too often.

This discussion also applies to neural nets and simulated annealing.

Now this article at least describes a problem for which a GA might actually be useful. Many such articles don't. But they haven't demonstrated that you need a bumpy hill-climbing algorithm.

This is why, despite all the hype, GAs, neural nets, and such aren't used all that much. The search space has to have the right properties. Not too small, not too big, bumpy, but not too bumpy.

Re:A note on hill-climbing

[55555]

Misses the point. GAs do not look at search spaces and ask 'is this function too bumpy'. GAs (as well as many other evolutionary algorithms, see GECCO [uiuc.edu]) are more similar to stochastic greedy strategies. I'd suggest looking at Walsh coefficients instead of derivatives as a rule of thumb.

A large part of the reason GAs aren't catching on more is that there aren't enough really good text books on them. All of the really useful information is still in the form of research papers, these things take time. Also,

Legos and Tron mentioned in his thesis

[the frizz]

The article link is light on details of the evolution algorithm, but Pablo Funes's home page [brandeis.edu] has the text of his thesis on Evolution of Complexity in Real-World Domains [brandeis.edu]. It talks about his use of evolving algorithms on topics like designing the strongest lego brick structure and playing Tron. Very cool, but not its application to caching.

The is even a link to an online Tron game [brandeis.edu] where us humans can play versus his evolving algorithms. The win/loss stats [brandeis.edu] for his algorithm is approaching even. Given that humans can also evolve in the Tron game play, I imagine that the algorithm will have a head start over the new influx of slashdot visitors and start to win more often than not over the next week. I never got to play though. The SQL db to mange the stats was already down then I tried.

This can't be legal

[TimCrider]

<sarcasm>
What happens if someone caches Metallica, or the new super hot J-Lo movie? Then how is the guy who brings the director a warm towel ever going to make his money?

You guys should really think before you go out and start making technology that blatently abuses copyrights

</sarcasm>

A new sorting algorithm also ...

[ThomasCR]

... has been evolved
with Critticall tool. [wikipedia.org]
Original site. [critticall.com]

50% of all bits

[TMacPhail]

50% of all bits sent over the internet are 0s. Just cache that and we have a 50% cache hit rate. :)

Security

[Door-opening Fascist]

The problem with caches is whether you can trust them. Even assuming you can keep the caches properly up-to-date, how do you prevent cache poisoning from taking place?

so far so good but..

[brunokummel]

Caching information can also be used as a backup of data in case the server crashes or has its data compromised by a virus , hacker, whatever you feel like ..
so what happens if you, for instance, have a security hole in one of your "smart" servers?? or even a breach in the protocol structure (DoS)?

you could get the server to "breed" algorithms that would stop all servers by either corrupting the data in all servers that are providing the service or just DoS-ing them.

I guess i'm not yet convinced that this solution is of any good for real world network which the whole structure is based on insecure protocols.
maybe after IPV6, IPV9, who knows?

Freenet

[zoeblade]

Doesn't Freenet [freenetproject.org] already do this within its own network?

Not such a great idea

[logicnazi]

I'm afraid this doesn't seem like a particularly appropriate use of genetic algorithims. In fact the entire piece seems to suggest a poor research project (someone who did genetic algorithms needed a thesis) which got picked up on a slow news day.

First of all I would point out that genetic algorithms are most appropriate for pure optimization problems with minimal mandatory constraints. While loading speed is important for internet caching it must be optimized inside certain constraints. A good cache s

Re:Sigh...

[snowlick]

The algorithm is just a standard ga, with the alleles being numeric values, not algorithms.

Re:Sigh...

[NoOneInParticular]

Actually, I have the real article here (not the New Scientist rubbish), the one they published at a conference, and what they do is evolve a function that takes the input data and computes a priority for that page. Pages with low priority are flushed, pages with high priority stay cached. One of the interesting expressions they found was:

priority = lastTimeAccessed * (distance - accessCount)

\ This was on data where the distance the document had travelled was taken into account. So, given some available

Re:*sigh*

[NialScorva]

Evolution is the change in allele frequencies over time. Pure and simple, that's all it is. Check any evolutionary biology book. The notion of giraffes sprouting gills is absurd and not even remotely what evolution is except in the creationist strawmen. What prevents a whole lot of small changes from adding up? No one has discovered a barrier or any reason that this wouldn't occur. It's like saying that water can move grains of sand, but there's no proof that a lot of water will eventually erode a beach.

The evolutionary algorithm will have a range of all possible algorithms that can be developed, so in a sense it is limited to "test various algorithms", though it would be testing all possible algorithms. Similarly biological evolution is limitted to testing various imperfect self-replicators, meaning all possible imperfect self-replicators. It is further constrained by the current state, but then that's the problem with non-biological GAs as well, the King of the Hill effect.

Skips too far forward

[Lulu of the Lotus-Ea]

Evolution is *not* the "change in allele frequencies over time." Or at least that's a secondary issue, historically, conceptually, and causitively. Well, on the last, allele frequency is pretty important (but still not exclusive). But evolution as a concept is firstly a question of PHENOTYPIC change, even before it's about GENOTYPIC change.

Evolution was a well known phenomenon (e.g. from the geological record) long before the work of Mendel was known. Specifically, the rather well known Darwin had no c

Re:Skips too far forward

[Dimensio]

Evolution is *not* the "change in allele frequencies over time."

"In fact, evolution can be precisely defined as any change in the frequency of alleles within a gene pool from one generation to the next."

- Helena Curtis and N. Sue Barnes, Biology, 5th ed. 1989 Worth Publishers, p.974

Overly simplistic

[Jonathan]

"In fact, evolution can be precisely defined as any change in the frequency of alleles within a gene pool from one generation to the next."

Yes, you *can* define evolution that way (to be precise, one group of biologists, the population geneticists, do define evolution that way). However, that's an entirely different statement than saying that's the *only* valid definition of evolution, which seems to be what you're implying.

As a molecular evolutionist, I find alleles to be too high level -- I deal with t

Re:Overly simplistic

[NialScorva]

Yeah, there are certainly other definitions. I didn't mean to state that as the only possible definition, only that it was the best description of modern evolutionary theory as applied to the current topic of conversation. I find the allele level interpretation much more useful as a parallel to GAs than a molecular, codon, or population level.

In the end, though, you can show that the molecular evolutionist and the zoologist's definitions are equivalent to the population geneticist definition, and vice ve

Re:*sigh*

[NialScorva]

No, it's not that simple. Evolution has been defined as changes adding up enough so that a single celled organism becomes a multi-celled organism, which develops RNA and DNA, which then grows in complexity to develop various "macro" level systems such as a cardio-pulminary system, a digestive tract, a nervous system, and a central control "brain" system. Each of these changes requires a macro change of which no predecessor exists in the current chain of organics.

That is one of the facts that it explains,

Re:*sigh*

[AKAImBatman]

That is one of the facts that it explains, not the definition. You're doing the equivalent of saying that a ball falling is the definition of gravity. Evolution is the collection of mechanisms by which these occur, which under the modern synthesis is by various alleles changing over time in a population.

My argument is that "micro-evolution" has not been shown to be the mechanism by which "macro-evolution" can occur. The results of environmental adaption and genetic mutations are well known, but no one h

Re:*sigh*

[Alexis de Torquemada]

For example, if humans lack the genome for an exoskeleton, and exoskeletons are "nature's selection" for space survivability, then the "micro-evolutionary theory" says that humans who live in space should eventually experience genetic mutations from which exoskeleton code will appear.

"All too often creationists spend their time arguing with a straw-man caricature of evolution."

Well put. [talkorigins.org]

Re:*sigh*

[NialScorva]

My argument is that "micro-evolution" has not been shown to be the mechanism by which "macro-evolution" can occur.

Define micro-evolution and macro-evolution and a set of criteria that a person could use to determine which of the two an adaptive event falls into.

For example, if humans lack the genome for an exoskeleton, and exoskeletons are "nature's selection" for space survivability, then the "micro-evolutionary theory" says that humans who live in space should eventually experience genetic mutations f

Re:*sigh*

[AKAImBatman]

I don't believe you understand the word "evolution". Evolution is not a huge jump that rapidly redefines something, it's an almost unnoticable change over time.

No, the current theories state that it is a unnoticable change over a long period of time. On a higher level, evolution simply states that major changes occurred over a long period of time. It also states that those changes occurred in an "organic vacuum". e.g. Lungs developed where no lungs had ever existed before.

Evolution can be understood as

Re:*sigh*

[Alexis de Torquemada]

Nothing "evolves" through the process, merely "adapts".

Nope. This is one and the same thing. E.g. there is plenty of molecular evidence that the blood clotting proteins forked off of pancreatic digestive enzymes by means of gene duplication and mutation. In embryonic development, some muscle cells are chemically activated to turn into bone cells. Archaeopteryx [talkorigins.org] is still a tell-tale example of a gradual transition between bipedal dinosaurs and birds.

Similarly, no code existed in nature for "micro-evolut

Re:*sigh*

[Conspiracy_Of_Doves]

ANY environmental adaptation of genetic code over multiple generations is evolution. It does not have to be a major change. BTW, creationists are the only ones that make a distinction between macro-evolution and micro-evolution. If fact, creationists are the only ones that I have ever heard use the terms.

Re:*sigh*

[Conspiracy_Of_Doves]

Natural selection is one of the methods (the other being sexual selection) by which all evolution (macro and micro) proceeds.

You forgot two.

[Alexis de Torquemada]

Natural selection is one of the methods (the other being sexual selection) by which all evolution (macro and micro) proceeds.

Mutation and genetic drift [talkorigins.org]. Also, the term natural selection as Darwin used it included sexual selection (besides ecological selection). The term is used to distinguish these kinds of naturally occuring selection from intentional breeding, which is called artificial selection.

Re:You forgot two.

[Conspiracy_Of_Doves]

Mutation is what all selection is based on, but you are right in that I forgot genetic drift.

Re:*sigh*

[Conspiracy_Of_Doves]

The two processes you are describing are the same thing. One simply takes a lot longer. Someone else in this thread made a great analogy about how saying that microevolution is possible while macroevolution is impossible is like saying that water can wash away individual grains of sand, but can't erode away a beach.

One of the problems with creationists is that they have a hard time conceiving of the incredibly vast amount of time that has passed which makes macroevolution possible.

I don't know where you

Re:*sigh*

[AKAImBatman]

The two processes you are describing are the same thing. One simply takes a lot longer.

No, they are theorized to be related. Macro level changes require a mechanism more sophisticated than that of "micro-evolution". "Micro-evolution" requires an existing genome from which to pull, and only allows for a small degree of genetic mutation. As I replied to another poster, Sickle-cell anemia is a perfect example of a mutation that "helps" by resisting malaria, but it has the side effect of an early death for th

Re:*sigh*

[pubjames]

I know I'm going to get myself into trouble for saying this, but "breeding" is NOT evolution!

That is a nonsensical statement. Breeding is fundamental to evolution, whether it be sexual reproduction or asexual splitting. Of course, breeding itself isn't evolution, but it is the process through which evolution occurs.

You seem to assume that the genes are unitary, descrete entities - that evolution occurs when, (to use your example) a giraffe suddenly gets the correct genes to develop gills. Genetics is mu

Re:*sigh*

[AKAImBatman]

Breeding is fundamental to evolution, whether it be sexual reproduction or asexual splitting.

Breeding is fundamental to life. Life is fundamental to evolution. Evolution tries to describe how organic soup could form simple organisms that become progressively more complex.

You seem to assume that the genes are unitary, descrete entities - that evolution occurs when, (to use your example) a giraffe suddenly gets the correct genes to develop gills. Genetics is much more complex than this.

Genetics is certa

Re:*sigh*

[GeckoUK]

Score:3 Insightful? when did creationist trolls become insightful?

Nature makes no distinction between your so called macro and micro-evolution. Rather there are to separate processes at work that combine to produce evolution.

1. Survival of the fittest (what you call environmental adaptation) starts with a population with a mixture of genes and states that those best able to reproduce in the current environment will probably make up a larger percentage of the next generation.

2. Genetic crossover during

Re:*sigh*

[AKAImBatman]

Sir, I requested intelligent discussion, but you yourself have taken to trolling. First you make an accusation ("creationist troll") which neither has any bearing on the subject, nor is in any way true. You will note that I never suggested that evolution is a "made up" process. That is outside the realm of this discussion. All I claimed is that the "Macro/Micro" division is an as-of-yet-unsupportable position that causes a great deal of confusion. The algorithm described in the article will not "evolve" in

Re:*sigh*

[ZigMonty]

Random mutations only gain you so much, and in all cases are also harmful in the same way they are helpful.

Why? Just because you give an example of where this is true (Sickle-cell anaemia), doesn't mean it is generally true. Why can't a random mutation be beneficial without bad side-effects? A random mutation can surely be harmful without good side-effects. Why not the reverse? It isn't a zero-sum game. Sure, the kind of mutation that is solely beneficial may be exceedingly rare, but that isn't proof that

Re:*sigh*

[AKAImBatman]

Will you make up your mind, first you agree with the grandparent poster that one particular example doesn't prove the general case, and then you make the claim that the SCA example does suggest the general case is zero sum.

I have made up my mind. The parent of my post made a statement that was factually correct: SCA does not "prove" that positive mutations can't happen. I then go on to show that everything from SCA to genetic manipulation has so far shown us that genetics is a zero sum game. It's perfect

Re:*sigh*

[The Cydonian]

I'm presuming you come from a biological background, but allow me to say this:- evolutionary programming is more about using evolution as a metaphor rather than modelling evolution per se. This I gathered after endless conversations with my (gastroenterologist) dad and (plant pathologist) mom on my research work in my final year of college.

Most computer scientists loosely use the term "evolutionary programming" to talk about algos that have inherently unpredictable ("emergent") results rather than modelling actual evolutionary processes observed in nature, although that's also a fair part of it all. (Incidentally, I also believe the "Science" topic assigned to this story is wrong for this reason.)

The meta-algo is evolutionary programming in that the algo fianlly "developed" by the meta-algo is apparently result that isn't immediately apparent, indeed, one that perhaps unpredictable by humans.

Re:*sigh*

[AKAImBatman]

I wish the mods had given you a +5. My peeve is exactly what you describe: that "evolution" is being used as an analogy rather than a realistic description of what it does. "Genetic Algorithms" is a fine name, and "breeding" is an accurate concept. But "evolving" is misleading to a very extreme degree. There's no need to describe the process as "evolution", yet CS researchers persist in doing so.

That being said, it can be a great tool for auto-adjusting software to its environment. If it works out, it may

Re:*sigh*

[StrawberryFrog]

Evolution implies ... e.g. An ameba suddenly mutates into a multi-celled configuration. Or a giraffe suddenly develops gills (Emphasis added).

Rubbish. There's nothing sudden implied.

Re:*sigh*

[Eevee]

I'd like to see an ameba gradually become multicelled. I just get this image of a far side cartoon of an ameba sitting around with a cup of coffee in the middle of meiosis, saying "I don't care if you haven't finished splitting off, I've got tickets to the ballgame so I'm dragging you along."

Re:*sigh*

[NoOneInParticular]

Easy: consider an amoeba sitting in a soup with millions of its cousins. Now consider an amoeba starting to huddle closer and closer to these cousins. Now it starts to cuddle with its children. Finally consider an amoeba that makes identical copies to cuddle up to. Cousins, children, self. Gradual evolution from a lot of related single cellular organisms to a single multi-cellular one.

Re:*sigh*

[Laxitive]

If you had studies GAs, you would know that GAs do "create" new information that doesn't exist in the original solution set (i.e. any given generation of potential solutions).

GA systems both propogate "good" information, as well as generate and test new information incrementally across generations. Of course, this is done within whatever limitations you choose to impose on the solution set (i.e. if you're using a fixed N-bit string to represent entities in the solution space, then you'll search across all 2^N possible solutions in the N-bit string space).

Fundamentally, GAs are just a way of searching a solution space for good solutions. They are slow, but can tackle a more diverse set of problems easier than the traditional backpropogation-based neural network. I would consider neural networks to be more in line with your description of an 'adapting' learning algorithm.

The following analogy can only be taken so far, but you can compare backpropogation-based neural networks to be akin to hill-climbing algorithms - you start from one solution, move some limited distance towards what you think is a better solution. For a neural network with N vertices, you can think of neural network learning as hill-climbing in an N-dimensional space over whatever field used to specify edge weights.

GAs, on the other hand, do a much more disparate search over any solution space. And it is surprising how well it finds near-optimal solutions even for problems where the relation between solutions is complex and non-intiuitive (e.g. minimums for seemingly chaotic functions).

-Laxitive

Re:*sigh*

[AKAImBatman]

They create new "information", not new "algorithms". Evolution supposes that organisms create new "biological processes", analogous to "algorithms".

Re:*sigh*

[Laxitive]

Algorithms are just a certain kind of information.

Consider a GA system that operated on bitstrings that are considered inputs to a universal turing machine. Then, the information created is an alrogithm.

True, when designing a GA system to do that, you might have problems in creating test cases for evaluating solution fitness, but that doesn't detract from the point.

There has been research done on using GAs on lisp-style expressions, using subexpression substitution instead of crossovers, to generate use

Re:*sigh*

[AKAImBatman]

The article and my own words stated the same thing. Information on the previous "generation" is used to adapt to the current environment. No "new" algorithm is "evolved", merely a new combination of existing algorithms.

As I understand it - from my reading of Climbing Mount Improbable by Dawkins - you've just described evolution. Perhaps you're using a different, far more strict definition of the word?

My statement is that "macro-evolution" is the basic concept of evolution. i.e. A single celled organism

Re:I've a question

[Fizzl]

Or SMTP? That's obsolete too!

Please people, before hitting submit, think atleast a second what you are saying.

"I have this hammer here. It's really handy for hitting nails."
"Oh cool, I have this piece of two-by-four here. Can I cut it in half with that?"

(If you did have some kind of point, please elaborate.)

not intelligent design

[CausticPuppy]

The evolution that is described in this article is anything but unguided. Researchers took existing carefully developed code. They selectively combined parts of this code. They studied the resulting effects to produce better code. This looks much more like Intelligent Design [discovery.org] than anything Chuck Darwin ever dreamed up.

No, if it were truly following the "intelligent design" theory, there wouldn't be any trial and error to begin with. The code would be written once, from the ground up, and