Optimization: Picking random keys from a dictionary and mutating values

[blaine]

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