AD: physics textbook question (statisical mechanics)

[Ageless the Drifter]

ah, I see what you mean, kind of a simulated annealing sort of set-up almost

I've got my probability of mutation down at 0.001, I was talking about the probability of a candidate parent getting spliced with another parent before going into the next generation rather than going in directly as a clone of the first selected parent. I know that too high a mutation rate is bad juju, but I don't remember whether or not there's an ideal cross-over rate.

[Agrulberry the Erudite]

oh, gotcha. people often set that probability at 1.0, but i don't think there's as general a consensus on it

however if you look up work on GAs used to solve the TSP before, you'd probably get some guidance that way on parameter settings

or you could be REALLY crazy and set up a GA to tune your GA

[Ageless the Drifter]

hah, oh man that's actually kind of a cool idea

[Ageless the Drifter]

I realized this morning that my crossover method was only producing one offspring from each pair of parents (like 000+111 ------> 011 or 100 but not both), so I fixed that and implemented elitism, and now the thing converges really quickly for 0<x<2048 and almost always to the exact optimum.

The literature I've found confirms that mutation in the form of local hill climbing is practically a necessity for GAs tackling the TSP. Overall nothing about the layout of this approach seems like it'll be too difficult to implement. Hopefully I can have a working code for the basic problem by like Wednesday and then I can kick back and spend the rest of the month noodling with it without having to worry about whether I'll have something to turn in. Should be a good month

[Agrulberry the Erudite]

nice.

i threw together the basics of a GA yesterday, trying to keep it as modular and general as i can for re-use. loads easier to do that in python than it would've been in C++; looking forward to connecting the GA up to my financial trading simulator for parameter tuning

[Ageless the Drifter]

Yeah I tried to modularize my GA for y=x so I could reuse as much of it as possible for the TSP, but I don't think much of it will be similar enough to just transplant it directly. I think I'm gonna just write this next one from scratch and hope that I can make it transplantable at least for variations of the TSP I might try to tackle later on.

[Agrulberry the Erudite]

I mostly hope to apply it to problems where crossover as usually applied is OK, or where I can find a non-standard representation of the problem where that's the case. As long as that's true, the primary thing that's application-specific is the fitness function, you know? Like, my simulation's fitness function is going to be pretty wild -- it'll have to run the simulator a bunch of times and take some measure of average deviation in the simulations from historical price data or something.

The other thing I've found is really easy with python is splitting shit up across multiple files. I put most of my functions in two separate files, and then the main procedural code in its own file, and "from function_filename import *" to lock them all together. It's so simple, and never yells at me.

[Ageless the Drifter]

ok what the fuck is with random.shuffle(x)

for some reason it works fine on its own but it absolutely will not work when I implement it in a while loop

[Agrulberry the Erudite]

could you post the code? never used shuffle before

[Agrulberry the Erudite]

this is a rlly neat sidebar

"Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated."

http://docs.python.org/library/random.html

[Ageless the Drifter]

random.shuffle(x) doesn't return anything, it just rearranges the entries in x, so that's why I defined shuffle(y), even though it shouldn't really be necessary.

Code: [Select]

def gen_pop(x):
        def shuffle(y):
               random.shuffle(y)
               return y
population=[]
while len(population)<popsize:
a=shuffle(x)
print a
population.append(a)
return population
x=[[7,9],[4,5],[1,1]] and this code returns

Code: [Select]

[[1, 1], [4, 5], [7, 9]]
[[1, 1], [4, 5], [7, 9]]
[[1, 1], [7, 9], [4, 5]]
[[1, 1], [7, 9], [4, 5]]
[[7, 9], [1, 1], [4, 5]]
[[1, 1], [4, 5], [7, 9]]
[[1, 1], [4, 5], [7, 9]]
[[1, 1], [4, 5], [7, 9]]
[[4, 5], [7, 9], [1, 1]]
[[7, 9], [4, 5], [1, 1]]
[[[7, 9], [4, 5], [1, 1]], [[7, 9], [4, 5], [1, 1]], [[7, 9], [4, 5], [1, 1]], [[7, 9], [4, 5], [1, 1]], [[7, 9], [4, 5], [1, 1]], [[7, 9], [4, 5], [1, 1]], [[7, 9], [4, 5], [1, 1]], [[7, 9], [4, 5], [1, 1]], [[7, 9], [4, 5], [1, 1]], [[7, 9], [4, 5], [1, 1]]]
so 'a' is getting shuffled before the print, but for some reason population just gets filled with identical copies of the original order of x

[Ageless the Drifter]

actually yeah that is really interesting. That sounds like it might become a stumbling block for my GA with large numbers of cities

[Agrulberry the Erudite]

i believe the trouble's here

"def shuffle(y):
               random.shuffle(y)
               return y"

random.shuffle(y) isn't actually altering its argument, y -- but it is returning something; it's returning the shuffled sequence, which you're not doing anything with, so it shuffles it then throws it away

you're right that you don't need to define this function, try deleting this function and changing your while loop to this:

while len(population)<popsize:
      a=random.shuffle(x)
      print a
      population.append(a)
   return population

alternatively you could use your shuffle function, but change

random.shuffle(y)

to

y=random.shuffle(y)

[Ageless the Drifter]

I don't think random.shuffle(x) returns anything. If you type

x=[a,b,c]
c=random.shuffle(x)
print c

into the shell and hit enter, it literally prints c -- just the letter c, not a permutation of x. If you just type in

x=[a,b,c]
random.shuffle(x)

into the shell and hit enter, it doesn't print anything (normally if you use a function in the shell it prints whatever the return is), but if you then type

x

and hit enter, x has been permuted

[Agrulberry the Erudite]

oh wow, you're right. how weird is that.

in that case the issue's that, since random.shuffle(x) or shuffle(x) doesn't return an argument,

a=shuffle(x)

has nothing to assign to a. instead of

a = shuffle(x)

try

shuffle(x)
a=x

?

edit: it might even be ok to just append x to the population after each new shuffle, and cut out the re-assignment to a entirely

[Ageless the Drifter]

I tried just doing

while blah blah
    population.append(shuffle(x))

and

y=x
while blah blah
     random.shuffle(y)
     population.append(y)

and even


while blah blah
     random.shuffle(x)
     population.append(x)

(although that one makes me nervous because it's important that the original copy of the argument list not be shuffled when all is said and done)

and a bunch of other variations and they all give me a list full of identical copies of the original x. I'm at a complete loss -- I'm asking the dudes over at xkcd/coding if they know what's up, but they're usually not very quick to respond.

[Ageless the Drifter]

ah, fuck it -- I made it work with random.sample(x,len(x)) -- good enough

[Agrulberry the Erudite]

haha k

sorry -- the issue is/was this:

http://od-eon.com/blogs/bogdan/python-assignment-value-or-reference/

what's being copied in the assignments are actual memory addresses, not values that are held in memory addresses, so you're making a bunch of copies of the same memory address over and over again

i know less about how to manage this issue in python versus C++, though (in C++ there are operators used to specifying when you want to assign or pass stuff by memory address instead of the more usual by value), so not sure but trying to figure out how to fix it

edit:

the problem emerges even in very simple examples, like

x=[5,6,3]
shuffle(x)
a=x
shuffle(x)
b=x

even here a and b always take the same values, because they literally refer to the same space in memory

[Grandasaur of the Egg]

Whether as a result of civil unrest, sweeping epidemics, economic collapse, foreign invasion or natural disaster, the Victorians were stalked by a fear of catastrophe. The pursuit of material values, even worldly success itself, seemed somehow to invite it. "Shall the Parthenon be in ruins on its rock — but these mills of yours be the consummation of the buildings of the earth, and their wheels be as the wheels of eternity?" asked Ruskin at the end of "Traffic," an address given at Bradford in 1864. "Catastrophe will come," he thundered, "or worse than catastrophe, slow mouldering and withering into Hades."

Among those who embodied this fear of catastrophe in fiction were George Chesney, author of The Battle of Dorking: Reminiscences of a Survivor (1871), who describes England as totally unprepared to confront the threat of German militarism, and H.G. Wells, whose War of the Worlds (1898) is written in the same kind of documentary style, and shows Surrey suburbanites caught equally unawares by Martian invaders. For his "scientific romances," and particularly for introducing aliens, Wells is hailed as the father of modern science fiction.

However, Richard Jefferies's After London; or Wild England predates The War of the Worlds by more than a decade. Published in 1885, it describes the ecological repercussions of some unspecified disaster, and posits a return to barbarism. England's lost towns have spewed out their mice and rats, pets and domestic animals have perished or reverted to a few wild breeds, and the overgrown countryside is now populated by lurking savages: Bushmen, Romanies and "foot gypsies." Descendants of the "ancients" live an embattled existence in settlements around a great inland lake, but little of the old civilisation remains: "There are few books, and still fewer to read them; and these are all in manuscript, for though the way to print is not lost, it is not employed since no one wants books" (Chaper 4). Although Jefferies did not foresee the space age, his novel is pioneering in another way, as an inspiration for the post-apocalyptic genre of science fiction.

Jefferies was influenced by Ruskin, to whom he refers, for example, in The Open Air (1885) and Field and Hedgerow (1889); his scenario is much closer than Wells's to the one Ruskin had warned of, and more alarming. After all, the Martians in The War of the Worlds are finally conquered by earth's bacteria, and London recovers. It is as busy as ever again by the end. Jefferies, on the other hand, grants it no reprieve. When his young hero, Sir Felix Aquila, makes a voyage of exploration across the inland lake, he reaches a putrid swamp which gives off noxious fumes. At one point, he traverses the marshy area on foot, hoping to find water to drink. Then, still parched with thirst, he returns to his canoe via the imprints of some skeletons which he had passed before:

The subtle poison of the emanations from the earth had begun to deaden his nerves. It seemed a full hour or more to him until he reached the spot where the skeletons were drawn in white upon the ground.

He passed a few yards to one side of them, and stumbled over a heap of something which he did not observe, as it was black like the level ground. It emitted a metallic sound, and looking he saw that he had kicked his foot against a great heap of money. The coins were black as ink; he picked up a handful and went on. Hitherto, Felix had accepted all that he saw as something so strange as to be unaccountable. During his advance into this region in the canoe he had in fact become slowly stupefied by the poisonous vapour he had inhaled. His mind was partly in abeyance; it acted, but only after some time had elapsed. He now at last began to realise his position; the finding of the heap of blackened money touched a chord of memory. These skeletons were the miserable relics of men who had ventured, in search of ancient treasures, into the deadly marshes over the site of the mightiest city of former days. The deserted and utterly extinct city of London was under his feet.

He had penetrated into the midst of that dreadful place, of which he had heard many a tradition: how the earth was poison, the water poison, the air poison, the very light of heaven, falling through such an atmosphere, poison. There were said to be places where the earth was on fire and belched forth sulphurous fumes, supposed to be from the combustion of enormous stores of strange and unknown chemicals collected by the wonderful people of those times. Upon the surface of the water there was a greenish-yellow oil, to touch which was death to any creature; it was the very essence of corruption. . . . [Chapter 23]

With what techniques, and how successfully, does Jefferies relate moral and physical corruption here? Compare this description with Ruskin's linkage of the "plague-wind" and "moral gloom" in "The Storm-Cloud of the Nineteenth Century" (a lecture given just a year before After London appeared). How might Felix's response to the scene heighten the effect on the reader? How relevant is the description to modern concerns?

Unlike the unfortunate foragers who had preceded him, Felix survives, and aims at the end to establish a kind of feudal utopia in another, idyllically rural, spot which he discovers. While it is rooted in Jefferies's own love of "Ancient Time," this aspect of his work also owes much to Ruskin, and is very much of the period: consider the medievalism of the Pre-Raphaelites, and Arts and Crafts organisations like the the Guild and School of Handicrafts. Whether Felix's venture succeeds or not is unknown, but the element of hope is enough for After London, despite its nightmarish vision of the submerged capital, to be classed as an early example of the "cosy catastrophe" subgenre. This is a term invented by Brian Aldiss in Billion Year Spree: The History of Science Fiction (1973) with reference to John Wyndham.

Jefferies had a personal reason for writing so vindictively about London. He seems to have blamed the city for his declining health. Moreover, he was writing at the time of the so-called Great Depression of 1873-1896. Like many lovers of the English countryside, he held London at least partly responsible for destroying the old ways of life there. Others who have swamped London in their work include Grant Allen, whose Strand Magazine story of December 1897, "The Thames Valley Catastrophe," describes a fiery flood of volcanic lava spewing over the area. "There was no more London," he says emphatically. More recently, J.G. Ballard's The Drowned World (1962) depicts London as submerged under a vast tropical swamp infested with iguanas, giant mosquitoes and so on. The protagonist, Dr Kerans, turns away from efforts to reclaim and loot the city, and heads south into the unreclaimed jungle. Compare and contrast the ambiguous endings of After London and The Drowned World.

[Agrulberry the Erudite]

here is a solution, just tried it with the simple a, b example:

http://stackoverflow.com/questions/845110/emulating-pass-by-value-behaviour-in-python

from copy import deepcopy
x=[6,5,3]
a=deepcopy(x)
random.shuffle(x)
b=deepcopy(x)

allows a and b to differ in value as desired

edit:

and

pop=[]
x=[1,2,3,4,5,6,7,8,9,10]
for i in range(10):
  shuffle(x)
  pop.append(deepcopy(x))
print(pop)

delivers a pop with lots of very different shuffled sequences in it

[Ageless the Drifter]

Huh. I'm really surprised I haven't tripped over that before now, if that's what's up, but that definitely explains it.

Appreciate the help

[Agrulberry the Erudite]

thanks for the problem, i'll be using deepcopy quite a lot now that i know about it

[Ageless the Drifter]

my python for computational science text just came in and now I'm compelled to start tacking on bells and whistles

I've been storing all my data right in the file -- eg my populations are all just list-type variables and my generation statistics are just lists of lists of statistics -- but now I kinda want to split the program into a method to write that stuff to files and then a method to extract it and print it in a visually-friendly form. I dunno if this is a worthwhile endeavor -- I suppose I could just make it reader-friendly without storing it in txt files, which would, I think, entail overhauling most of the actual mechanics of the code I've written so far.

I feel like it'd be a good thing to get around to now, though -- like I might start running into problems trying to store everything in variables when the city number gets large enough.

[Agrulberry the Erudite]

do it

file I/O is stupid easy in python

let me know how that book is btw. i have these two and they're not bad:

http://www.amazon.com/Programming-Python-Mark-Lutz/dp/0596158106/ref=sr_1_1?s=books&ie=UTF8&qid=1326742928&sr=1-1

http://www.amazon.com/Learning-Python-Powerful-Object-Oriented-Programming/dp/0596158068/ref=pd_sim_b_1

[Ageless the Drifter]

blargh I've wasted like the whole day trying to write this so I can

a) set the file names via command line arguments
b) verify whether the specified filenames already exist and prompt a new filename choice if so

and have run into all kinds of crazy behavior. There must be a better way to do this -- I think maybe I should just have the filename set automatically and avoid the whole raw_input thing (not that I think that's the source of the problem) but I want to be able to run the program over and over and have unique files for every instance, so I've gotta figure out how to make sure the files are named differently (preferably indexed in some way by iteration number, or maybe the filenames could be all the same at each iteration of the program, but grouped in indexed folders).

I think as far as actually processing the information I'm gonna keep everything in variables the way I've been programming before today (but still write files storing the data) -- the book I picked up gives this whole schpiel about how to put your shit into folders and then the very next section is how to get shit out of the folders and into variables because it's easier to process that way. Guess I should've read ahead a bit.

[Ageless the Drifter]

Huzzah, finally got that shit. I think I've just been sitting here too long today, the fix was really obvious

[Ageless the Drifter]

Oh man I finished my edge recombination cross-over  algorithm. Just gotta write a hill-climb and I can stick a fork in this bitch 

[Agrulberry the Erudite]

nice work dude

totally called it on there being cross-over operators specifically for TSP btdubs /patselfonback

[Ageless the Drifter]

yeah, I found a goldmine academic paper that surveyed the different types and their efficacy in producing optimal solutions. This was easily the most complicated to script, but supposedly almost always finds very-near global optima for medium-sized maps, whereas the rest sound like they have almost-not-worth-the-effort outcomes, on average, (although some of them are apparently ok (but still not terrific) if you also implement like parallel processing of discrete populations and then occasionally swap an offspring or two from each population.) so I said fuck it.

Still not 100% on how to implement the hill-climb effectively, since "1-mutant neighbors" is kind of a fuzzy term for combinatorial problems. I guess it would be a path with two cities swapped, but the number of such neighbors grows factorialy with the size of the map, so that would be really inefficient. I guess maybe I could pick one allele and only look at neighbors that swap out that specific allele, over and over until I hit an optima. All signs point to hill-climbs being pretty much mandatory for this GA to be effective. Or maybe I'll luck out and find a paper that surveys TSP hill-climbing methods.

[Agrulberry the Erudite]

Still not 100% on how to implement the hill-climb effectively, since "1-mutant neighbors" is kind of a fuzzy term for combinatorial problems. I guess it would be a path with two cities swapped, but the number of such neighbors grows factorialy with the size of the map, so that would be really inefficient.

this seems like a reasonable definition of 1-mutant neighbor to me

for a map with N cities there should be on the order of N^2 possible such two-city swaps; what do you mean it grows factorially?