473,287 Members | 3,295 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,287 software developers and data experts.

Optimization: Picking random keys from a dictionary and mutatingvalues

Hey everyone,
Just a friendly question about an efficient way to do this. I have
a graph with nodes and edges (networkx is am amazing library, check it
out!). I also have a lookup table with weights of each edge. So:

weights[(edge1, edge2)] = .12
weights[(edge2, edge5)] = .53
weights[(edge5, edge1)] = 1.23
weights[(edge3, edge2)] = -2.34
etc.

I would like to take this weight table and subject it to evolutionary
mutations. So given a probability p (mutation rate), mutate edge
weights by some random value. So in effect, if p is .25, choose 25%
random edges, and mutate them some amount. So:
1. Whats a good way to get the keys? I'm using a loop with
random.choice() at the moment.
2. Any comments on how to get a 'fair' mutation on an existing edge
value?

I currently am doing something like this, which seems like it leaves
something to be desired.

import random
weights = generateweights() # generates table like the one above
p = 0.25
v = random.betavariate(2, 10)
num = int(v*len(weights)) # How many weights should we mutate?
keys = w.keys()
for i in xrange(num):
val = random.choice(keys) # Choose a single random key
w[val] = w[val]*(random.random()*5-1) # Is this a 'good' way to
'mutate' the value?

This is an evolutionary search, so mutate in this sense relates to a
genetic algorithm, perhaps a gradient decent?
Thanks!
Blaine
Jun 27 '08 #1
2 1787
On May 28, 4:41*pm, blaine <frik...@gmail.comwrote:
1. *Whats a good way to get the keys? I'm using a loop with
random.choice() at the moment.
Why not keep a separate list of keys and use random.sample()?
Raymond
Jun 27 '08 #2
On May 28, 7:41 pm, blaine <frik...@gmail.comwrote:
Hey everyone,
Just a friendly question about an efficient way to do this.
Friendly advance reminder: in many optimization problems, the
objective function is far more expensive to calculate than the
optimizing procedure. Your time is usually better spent optimizing
the objective function, or tuning the optimizer.

But what they hey.
I have
a graph with nodes and edges (networkx is am amazing library, check it
out!). I also have a lookup table with weights of each edge. So:

weights[(edge1, edge2)] = .12
weights[(edge2, edge5)] = .53
weights[(edge5, edge1)] = 1.23
weights[(edge3, edge2)] = -2.34
etc.

I would like to take this weight table and subject it to evolutionary
mutations. So given a probability p (mutation rate), mutate edge
weights by some random value. So in effect, if p is .25, choose 25%
random edges, and mutate them some amount. So:
1. Whats a good way to get the keys? I'm using a loop with
random.choice() at the moment.
That's probably the best way.

You might be able to squeeze a little more speed out of it by using a
partial random shuffle as opposed to removing the item from the list.
This will minimize the amount of copying. Here's an example (without
error checking):

def partial_random_shuffle(lst,nshuffled):
for i in xrange(nshuffled):
j = random.randrange(i,len(lst))
t = lst[i]
lst[i] = lst[j]
lst[j] = t

The first nshuffled items of lst upon return will be the selected
items. Note: This might also be slower than removing items. It
should scale better, though.

2. Any comments on how to get a 'fair' mutation on an existing edge
value?
random.normalvariate is usually a good choice for selecting random
real-valued increments.

val = random.normalvariate(val,sigma)

where sigma, the standard deviation, is the amount

I currently am doing something like this, which seems like it leaves
something to be desired.

import random
weights = generateweights() # generates table like the one above
p = 0.25
v = random.betavariate(2, 10)
num = int(v*len(weights)) # How many weights should we mutate?
keys = w.keys()
for i in xrange(num):
val = random.choice(keys) # Choose a single random key
w[val] = w[val]*(random.random()*5-1) # Is this a 'good' way to
'mutate' the value?
If you don't remove keys[val], there's a chance you'll mutate the same
key twice, which I doubt is what you want.

This is an evolutionary search, so mutate in this sense relates to a
genetic algorithm, perhaps a gradient decent?
A gradient descent method is not an evolutionary search and involves
no randomness (unless noise is added to the objective, which is a
possible way to attack a function with unimportant small scale
features, and in that case normalvariate would be the thing used).

Carl Banks
Jun 27 '08 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
by: r.e.s. | last post by:
Would anyone care to offer pointers on how the following code might be optimized? Or alternatives? ... --- def lz(string): """ Return the Lempel-Ziv complexity (LZ78) of string. """ ...
57
by: Egor Bolonev | last post by:
why functions created with lambda forms cannot contain statements? how to get unnamed function with statements?
5
by: Tor Erik Sønvisen | last post by:
Hi How can I select a random entry from a dictionary, regardless of its key-values? regards tores
90
by: Christoph Zwerschke | last post by:
Ok, the answer is easy: For historical reasons - built-in sets exist only since Python 2.4. Anyway, I was thinking about whether it would be possible and desirable to change the old behavior in...
5
by: Bob Kline | last post by:
I have a suggestion for speeding up the performance of code like this: fields = cgi.FieldStorage() if fields: ... which, as it turns out, invokes FieldStorage.__len__(), which in turn calls...
39
by: Alan Isaac | last post by:
This may seem very strange, but it is true. If I delete a .pyc file, my program executes with a different state! In a single directory I have module1 and module2. module1 imports random and...
3
by: David | last post by:
On Sun, May 4, 2008 at 4:43 AM, lev <levlozhkin@gmail.comwrote: Hi, I started tidying up the script a bit, but there are some parts I don't understand or look buggy. So I'm forwarding you the...
13
by: Nader | last post by:
Hello, I have a dictionary and will get all keys which have the same values. d = {('a' : 1), ('b' : 3), ('c' : 2),('d' : 3),('e' : 1),('f' : 4)} I will something as : d.keys(where their...
3
by: Michel Esber | last post by:
Hi all, Db2 v8 FP15 LUW . create table T (ID varchar (24), ABC timestamp) There is an index for (ID, ABC), allowing reverse Scans. My application needs to determine MIN and MAX(ABC) for a...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.