-
9 votes
-
DJ Shadow - Stem/Long Stem (1996)
8 votes -
Albert Einstein's relativity document gifted to Nobel museum
4 votes -
Secrets and lies at Guantanamo Bay: Listening devices, FBI informants, and gag orders… these are just some of the ways that the US is mishandling classified information in the Al Qaeda trials
5 votes -
Genetic Algorithms
Introduction to Genetic Algorithms Genetic algorithms can be used to solve problems that are difficult, or impossible to solve with traditional algorithms. Much like neural networks, they provide...
Introduction to Genetic Algorithms
Genetic algorithms can be used to solve problems that are difficult, or impossible to solve with traditional algorithms. Much like neural networks, they provide good-enough solution in short amount of time, but rarely find the best one. While they're not as popular as neural networks nor as widely used, they still have their place, as we can use them to solve complicated problems very fast, without expensive training rigs and with no knowledge of math.
Genetic algorithms can be used for variety of tasks, for example for determining the best radio antenna shape, aerodynamic shapes of cars and planes, wind mill shapes, or various queing problems. We'll use it to print "Hello, World!".
How does it work?
Genetic algorithm works in three steps.
- Generate random solutions
- Test how good they are
- Pick the best ones, breed and mutate them, go to step 2
It works just like evolution in nature. First, we generate randomised solutions to our problem (in this case: random strings of letters).
Then, we test each solution and give it points, where better solutions gain more points. In our problem, we would give one point for each correct letter in the string.
Afterwards, we pick the best solutions and breed it together (just combine the strings). It's not bad idea to mutate (or randomize) the string a bit.
We collect the offsprings, and repeat the process until we find good enough solution.
Generate random solutions
First of all, we need to decide in which form we will encode our solutions. In this case, it will be simply string. If we wanted to build race cars, we would encode each solution (each car) as array of numbers, where first number would be size of the first wheel, the second number would be size of the second wheel, etc. If we wanted to build animals that try to find food, fight and survive, we would choose a decision tree (something like this).
So let's start and make few solutions, or entities. One hundred should be enough.
from random import randint goal = "Hello, World!" allowed_characters = list("qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM ,!") def get_random_entity(n, string_length): entities = [] for _ in range(0, n): entity = "" for _ in range(0, string_length): entity += allowed_characters[randint(0, len(allowed_characters)-1)] entities.append(entity) return entities print(get_random_entity(100, 13))
Test how good they are
This is called a "fitness function". Fitness function determines how good a solution is, be it a car (travel distance), animal (food gathered), or a string (number of correct letters).
The most simple function we can use right now will simply count correct letters. If we wanted, we could make something like Levenshtein distance instead.
def get_fitness(entity): points = 0 for i in range(0, len(entity)): if goal[i] == entity[i]: points += 1 return points
Crossover and mutation
Now it's time to select the best ones and throw away the less fortunate entities. Let's order entities by their fitness.
Crossover is a process, when we take two entities (strings) and breed them to create new one. For example, we could just give the offspring one part from one parent and another part from second parent.
There are many ways how to do this, and I encourage you to try multiple approaches when you will be doing something like this.
P: AAAABBB|BCCCC P: DDDDEEE|FGGGG F1: AAAABBB|FGGGG
Or we can just choose at random which letter will go from which parent, which works the best here. After we have the offsprint (
F1
), we should mutate it. What if we were unfortunate, andH
(which we need for ourHello, World!
) was not in any of the 100 entities? So we take the string and for each character of the string, there is a small chance to mutate it - change it at random.F1: ADDDEBEFGCGG F1`: ADHDEBEFGCGG
And it's done. Now kill certain part of old population. I don't know which percentage is best, but I usually kill about 90% of old population. The 90% that we killed will be replaced by new offsprings.
There is just one more thing: which entities do we select for crossover? It isn't bad idea - and it generally works just fine - to just give better entities higher chance to breed.
def get_offspring(first_parent, second_parent, mutation_chance): new_entity = "" for i in range(0, len(first_parent)): if randint(0, 100) < mutation_chance: new_entity += allowed_characters[randint(0, len(allowed_characters)-1)] else: if randint(0, 1) == 0: new_entity += first_parent[i] else: new_entity += second_parent[i] return new_entity
When we add everything together, we get this output:
Generation 1, best score: 2 ::: QxZPjoptHfNgX Generation 2, best score: 3 ::: XeNlTOQuAZjuZ Generation 3, best score: 4 ::: weolTSQuoZjuK Generation 4, best score: 5 ::: weTgnC uobNdJ Generation 5, best score: 6 ::: weTvny uobldb Generation 6, best score: 6 ::: HellSy mYbZdC Generation 7, best score: 7 ::: selOoXBWoAKn! Generation 8, best score: 8 ::: HeTloSoWYZlh! Generation 9, best score: 8 ::: sellpX WobKd! Generation 10, best score: 9 ::: welloq WobSdb Generation 11, best score: 9 ::: selloc WoZjd! Generation 12, best score: 10 ::: wellxX WoVld! Generation 13, best score: 10 ::: welltX World! Generation 14, best score: 10 ::: welltX World! Generation 15, best score: 10 ::: welltX World! Generation 16, best score: 11 ::: zellov Wobld! Generation 17, best score: 11 ::: Hellty World! Generation 18, best score: 11 ::: welloX World! Generation 19, best score: 11 ::: welloX World! Generation 20, best score: 11 ::: welloX World! Generation 21, best score: 12 ::: welloX World! Generation 22, best score: 12 ::: Helloy World! Generation 23, best score: 12 ::: Helloy World! Generation 24, best score: 12 ::: Helloy World! Generation 25, best score: 12 ::: Helloy World! Generation 26, best score: 12 ::: Helloy World! Generation 27, best score: 12 ::: Helloy World! Generation 28, best score: 12 ::: Helloy World! Generation 29, best score: 12 ::: Helloy World! Generation 30, best score: 12 ::: Helloy World! Generation 31, best score: 12 ::: Helloy World! Generation 32, best score: 12 ::: Helloy World! Generation 33, best score: 12 ::: Helloy World! Generation 34, best score: 13 ::: Helloy World! Generation 35, best score: 13 ::: Hello, World!
As we can see, we find pretty good solution very fast, but it takes very long to find perfect solution. The complete code is here.
Maintaining diversity
When we solve difficult problems, it starts to be increasingly important to maintain diversity. When all your entities are basically the same (which happened in this example), it's difficult to find other solutions than those that are almost the same as the currently best one. There might be a much better solution, but we didn't find it, because all solutions that are different to currently best one are discarded. Solving this is the real challenge of genetic algorithms. One of the ideas is to boost diverse solutions in fitness function. So for every solution, we compute distance to the current best solutions and add bonus points for distance from it.
20 votes -
From two bulls, nine million dairy cows
5 votes -
Generative Adversarial Networks - The story so far
6 votes -
Italy beats Sweden to host 2026 Winter Olympics
7 votes -
How Verizon and a BGP optimizer knocked large parts of the internet offline today
14 votes -
Ann Sarnoff named Warner Bros. CEO in surprise pick
3 votes -
The history of the Elite Beat Agents / Osu! Tatakae! Ouendan series
5 votes -
How the Swedish town of Eskilstuna became the world capital of recycling
5 votes -
In the largest protests in decades, Czechs demand resignation of prime minister
8 votes -
Dutch telephone outage takes out nation’s emergency number for over three hours
9 votes -
Every way to cook a potato (sixty-three methods) | Bon Appétit
4 votes -
A crispy, salty, American history of fast food
3 votes -
What is a scam that people should know about?
There are, sadly, far too many people and companies out there more than willing to take advantage of people. Fortunately, awareness is usually a good defense. What are some scams that we should...
There are, sadly, far too many people and companies out there more than willing to take advantage of people. Fortunately, awareness is usually a good defense. What are some scams that we should all know about so that we don't fall for them?
38 votes -
"13 Minutes to the Moon" - BBC documentary podcast on Apollo 11
7 votes -
Digging deeper into Pompeii's past
6 votes -
9 top subreddits for tech sustainability enthusiasts
2 votes -
Trey Anastasio on the endurance of jam bands and the life of Phish
4 votes -
Pastry chef, Claire Saffitz, attempts to make "gourmet" Starburst | Gourmet Makes
6 votes -
The Cube Rule of food identification
22 votes -
A fundamentalist community forges a new identity: Hildale and Colorado City, born of fundamentalist LDS doctrine, are rebuilding themselves—but not without holding on to their core beliefs
8 votes -
Can you make one million layer puff pastry by hand?
8 votes -
"Shona is one of the almost 50 people worldwide known as skyborns—impromptu deliveries who increase the passenger manifest, mid-flight."
4 votes -
You can sue media companies over Facebook comments from readers, Australian court rules
13 votes -
This week's album and EP releases
Here's a list of a things that came out in this past week, up through Friday. Of course, there's no way to be completely comprehensive with this and I avoided including things where information...
Here's a list of a things that came out in this past week, up through Friday. Of course, there's no way to be completely comprehensive with this and I avoided including things where information was too lacking, so feel free to mention anything that isn't on here that you think is worth mentioning. Beyond that, if you have any thoughts of any of these albums, it would be great to hear them :)
Artist Title Genre(s) Song Link Aaron Watson Red Bandana Country Song.link Antwood Alousia EP IDM, Electro, UK Bass Song.link B. o. B Southmatic Southern Hip Hop Song.link Bedouine Bird Songs of a Killjoy Singer/Songwriter, Chamber Folk Song.link Benny the Butcher The Plugs I Met East Coast Hip Hop, Hardcore Hip Hop, Boom Bap Song.link black midi Schlagenheim Experimental Rock, Math Rock, Noise Rock Song.link Black Pumas Black Pumas Soul Song.link Buddy & Julie Miller Breakdown on 20th Ave. Americana, Country Song.link Car Seat Headrest Commit Yourself Completely Indie Rock, Power Pop Song.link Charnett Moffett Bright New Day Jazz Song.link Collective Soul Blood Pop Rock, Alternative Rock Song.link Craig Xen Broken Kids Club Southern Hip Hop, Trap Metal Song.link DJ JM No Days Off EP Tribal House Song.link Decent Criminal Bliss Pop Punk, Alternative Rock Song.link Diabolic The Disconnect East Coast Hip Hop, Hardcore Hip Hop Song.link Diplomats of Solid Soud A Higher Place Rhythm & Blues, Soul Song.link Drivin'-n-Cryin' Live The Love Beautiful Hard Rock, Roots Rock Song.link Emily Burns PDA EP Electropop Song.link Erin Durant Islands Indie Folk, Country Song.link Fences Failure Sculptures Indie Pop, Indie Folk Song.link Fruit Bats Gold Past Life Indie Pop, Indie Folk Song.link Ghostemane & Parv0 Human Err0r EP Trap Metal Song.link Gorilla Treecreeper Hard Rock Song.link Gucci Mane Delusions of Grandeur Southern Hip Hop, Trap rap Song.link Hackensaw Boys A Fireproof House Of Sunshine EP Bluegrass Song.link Harry And The Potters Lumos Indie Pop Song.link Hatchie Keepsake Dream Pop, Shoegaze Song.link Hollywood Vampires Rise Hard Rock Song.link Holy Ghost! Work Dance-Pop, Synthpop, Nu-Disco Song.link Hot Chip A Bath Full of Ecstasy Indietronica, Synthpop Song.link Idris Elba Idris Elba Presents: The YARDIE Mixtape Hip Hop Soundcloud ILOVEMAKONNEN M3 EP Cloud Rap, Alternative R&B Song.link Jim Lauderdale From Another World Bluegrass, Country Song.link Joey Trap Trap Jack 2.5 Trap Rap Song.link Josh A & iAmJakeHill Save Our Souls Pop Rap, Trap Rap Song.link K Camp Wayy 2 Kritical Trap Rap, Pop Rap Song.link lilbootycall Jesus Said Run It Back Cloud Rap Song.link Lil Nas X 7 EP Trap Rap Song.link Los Retros Retrospect EP Indie Pop Song.link Los Straitjackets Channel Surfing EP Pop Rock, Surf Rock Song.link Mannequin Pussy Patience Power Pop, Indie Rock Song.link Mark Ronson Late Night Feelings Dance-Pop Song.link Mr. Hudson WHEN THE MACHINE STOPS Electropop Song.link Pell Gravity Southern Hip Hop Song.link Pi'erre Bourne The Life of Pi'erre 4 Pop Rap, Trap Rap Song.link Randy Newman Toy Story 4 (Original Motion Picture Soundtrack) OST, Film Soundtrack Song.link Red Velvet 'The ReVe Festival' Day 1 EP K-Pop, Dance-Pop, Electropop Song.link Richard Reed Parry Quiet River Of Dust Vol. 2: That Side of the River Indie Folk, Chamber Folk Song.link Rob Burger The Grid Chamber Jazz Song.link Russian Girlfriends In The Parlance Of Our Times Punk Rock Song.link SF9 RPM EP K-Pop, Electropop Song.link SG Lewis Dawn EP Alternative R&B, Deep House Song.link SG Tip Block Boy 2 Trap Rap Song.link Stray Kids Clé 2 : Yellow Wood K-Pop, Dance-Pop Song.link The Raconteurs Help Us Stranger Alternative Rock, Blues Rock Song.link The Rhythm Method How Would You Know I Was Lonely? Alternative Dance Song.link The Rolling Stones Bridges To Bremen (Live) Hard Rock, Blues Rock Song.link The Underachievers Lords Of Flatbush 3 Trap Rap, East Coast Hip Hop Song.link Titus Andronicus An Obelisk Indie Rock, Punk Rock Song.link Trina The One Pop Rap, Southern Hip Hop Song.link Two Door Cinema Club False Alarm Indie Pop Song.link Willie Nelson Ride Me Back Home Country, Standards Song.link YFN Lucci 650Luc: Gangsta Grillz Trap Rap Song.link
Notes:
If you spot any mistakes, let us know.
Parental Advisory version of all albums linked (so NSFW).Ghostemane & Parv0 - Human Err0r | Song.link says Single but is actually EP.
Idris Elba Presents: The YARDIE Mixtape | No song.link. Can't find anywhere. Linked his record label's official soundcloud, since that's where the other Idris Elba Presents are located, so I assume this one will show up there eventually too.12 votes -
Tildes from the command line
How many people would be interested in browsing Tildes from a TUI, ala rtv?
21 votes -
What are the absolute worst VPN's you should never use?
Many good VPN's and bad VPN's exist, which fall under bad VPN'S?
22 votes -
Do you play your games modded or vanilla and why?
I personally usually heavily mod my games, due to finding the process of modding itself fun, along with me preferring to spend a LONG time at one run through. As an example, I'd give minecraft...
I personally usually heavily mod my games, due to finding the process of modding itself fun, along with me preferring to spend a LONG time at one run through.
As an example, I'd give minecraft where I usually play so-called expert packs, which are basically taking a lot of mods and making them depend on each other for progression.
22 votes -
Earthquake of 7.5-magnitude hits eastern Indonesia, tremors felt in Australia
8 votes -
The new drug highway: Pacific islands at centre of cocaine trafficking boom
5 votes -
More than 1,000 couples got married in Taiwan's first month of equal marriage
12 votes -
Need advice for simple speaker setup
I just moved into a new apartment, and am using a 32" tv in the living room. The TV is already way too small, but I'd rather prioritize spending on the speakers first. I thought I could live with...
I just moved into a new apartment, and am using a 32" tv in the living room. The TV is already way too small, but I'd rather prioritize spending on the speakers first.
I thought I could live with the TV speakers, but have quickly realized that they have made watching movies impossible. The dialogue is impossible to hear without cranking up the volume. And then if there is anything other than dialogue, it's way too loud.
The walls in the apartment are fairly thin, so I'm pretty sure a subwoofer is out of the question. So I was looking at soundbars but keep seeing conflicting advice. There are articles like this that make them sound fine, yet when you go to place like /r/hometheater, everyone despises them.
So my next step was to look at powered bookshelf speakers. They seemed like a pretty good option, until I went to best buy to listen to them. I'm not sure if they just weren't set up properly or what, but none of them sounded that great. Especially when compared to the tower speakers they had.
So now I'm at a loss. Should I go with a soundbar, bookshelf, or tower speakers? My budget is under $500.
10 votes -
I’m a journalist but didn't fully realize the terrible power of US border officials until they violated my rights and privacy
41 votes -
Axios releases nearly 100 leaked internal vetting documents of top Donald Trump administration officials, showing "red flags" deliberations
12 votes -
The researcher behind the smartphone “horns” study sells posture pillows
23 votes -
Any hams around?
So, I am far from the most experienced, or the most knowledgeable, or the most active amateur radio operator out there, but it is something that has piqued my interest none the less. Before I got...
So, I am far from the most experienced, or the most knowledgeable, or the most active amateur radio operator out there, but it is something that has piqued my interest none the less. Before I got into the hobby, I always assumed that the FCC just game amateurs a small bucket of useless spectrum and that was it. Maybe you could fly an RC plane, but surely that is about as cool as it gets.
It turns out I was dead wrong. Amateurs are allocated bands all across the RF spectrum - more or less. Bands from way below the AM broadcast frequency to way above the microwave frequencies used by our cell phones and wireless routers. Also, you are allowed to legally transmit at up to 1.5 kilowatts of power! That's 3,000 times as much power as your average walkie talkie! :) Also, importantly, the license exam only costs $15.
At many of the lower frequencies, the signals bounce off the ionosphere and you can make contact with people all over the world (propagation gods permitting). At the higher frequencies, you lose that "skip propagation," but more bandwidth is available. There are analog voice repeater networks, digital packet networks, mesh networks running on modified commercial WiFi gear, and even a handful of old school packet BBSes. There are some LEO satellites which run voice repeaters which allow you make international contacts, and sometimes even the International Space Station will participate in events. Lots of cool stuff going on. This hobby is kind of a bottomless rabbit hole of possibilities.
I got my technician license about a year ago, and I have been most interested in the data networking end of the hobby. Despite being a pile of hacks, APRS is still very cool, and sometime soon I hope to set up an AREDN node of my own. Every once in a while I'll call into the local repeaters and shoot the breeze.
So there's my story. Are there any other hams out there?
25 votes -
The health benefits of sauna use
7 votes -
Ravelry (a popular site/community for knitting and crocheting) bans posts in support of Trump or his administration
20 votes -
Charlottesville white supremacist who killed protester asks judge for mercy and a sentence shorter than life in prison
14 votes -
UK forms citizens’ assembly on climate change
7 votes -
Compton's Cafeteria riot: A historic act of trans resistance, three years before Stonewall
10 votes -
The case for reparations
7 votes -
Citizens on patrol: What if your neighbor could give you a parking ticket?
9 votes -
How 3D printing could help shape surgery
5 votes -
'It's totally unfair': Chicago, where the rich live thirty years longer than the poor
7 votes -
New York is sixth state to outlaw gay and trans 'panic defenses'
13 votes -
What's the best advice you've been given regarding photography?
I'm interested in what you all have heard over the years or have learned on your own, that has stuck with you and made you a better photographer
16 votes