I'm playing around with genetic algorithms and I want to write a
function that mutates an integer by iterating across the bits, and about
1 in 10 times, it should switch a zero to a one, or a one to a zero.
I'm not sure how many bits are inside a python integer. The library
reference says at least 32.
I'm thinking about writing a function that eats integers and poops out
lists of bools; and then I can iterate through that, and change values
in there. But before I do that, does anyone have a better idea? 12 11651
Matthew Wilson <mw*****@sarcastic-horse.com> writes: I'm playing around with genetic algorithms and I want to write a function that mutates an integer by iterating across the bits, and about 1 in 10 times, it should switch a zero to a one, or a one to a zero.
I'm not sure how many bits are inside a python integer. The library reference says at least 32.
Long ints can have as many bits as you want.
I'm thinking about writing a function that eats integers and poops out lists of bools; and then I can iterate through that, and change values in there. But before I do that, does anyone have a better idea?
Just shift and mask. Untested code:
def bit_stream(n):
p = 1
while p < n:
bit = (n & p) != 0
if rand() % 10 == 0:
bit = not bit
p = p * 2
yield bit
The above assumes you want to look at the bits sequentially, so it
doesn't try to change them inside the number, which would mean consing
up a new number every time a bit changes. If you want to look at them
all at once, your idea of making a list of bools and flipping a subset
of them is reasonable. An optimization for long ints would be use the
array module, convert your integer to an array, do a bunch of bit
flips in the array, and convert back.
> I'm thinking about writing a function that eats integers and poops out lists of bools; and then I can iterate through that, and change values in there. But before I do that, does anyone have a better idea?
For speed, you should use shift and boolean ops - like this:
def mutate(seq, n=32, prob=0.05):
for bit in xrange(n):
if random.random() <= prob:
seq ^= 1 << bit
return seq
Regards,
Diez
Matthew> I'm playing around with genetic algorithms and I want to write
Matthew> a function that mutates an integer by iterating across the
Matthew> bits, and about 1 in 10 times, it should switch a zero to a
Matthew> one, or a one to a zero.
Just use Python's bitwise ops, for example: x = 0x0FFFCCCC hex(x)
'0xfffcccc' hex(x | (1 << 13))
'0xfffeccc'
Skip
Paul Rubin wrote: Matthew Wilson <mw*****@sarcastic-horse.com> writes:
I'm playing around with genetic algorithms and I want to write a function that mutates an integer by iterating across the bits, and about 1 in 10 times, it should switch a zero to a one, or a one to a zero.
I'm not sure how many bits are inside a python integer. The library reference says at least 32.
Long ints can have as many bits as you want.
Such as -1L which has an infinite number of bits.
I have used a list of integers as my defacto standard for representing a
stream of bits. On my windows box this is slower than using a long
integer but with psyco running (psyco.sourceforge.net) it is faster than
the long integer implementation.
It also is faster to bail out on a comparison, for example
if (a&b)!= 0:
can be optimized to fail on the first integer failure, it doesn't have
to complete the operation as it would with a long integer.
This is useful when seeing if a bit string is contained inside another
bit string.
Matthew Wilson: I'm not sure how many bits are inside a python integer. The library reference says at least 32.
Platform dependent. Could be 64 on 64 bit machines.
I'm thinking about writing a function that eats integers and poops out lists of bools; and then I can iterate through that, and change values in there. But before I do that, does anyone have a better idea?
Python isn't good for that sort of low-level bit twiddling.
Here's another possibility. Use a long int as your genome,
then make a new long int which describes the bits which
need to be inverted, then apply an xor between them.
import random
def toLSBBinary(x, num_bits):
letters = []
for i in range(num_bits):
if x & (1L << i):
letters.append("1")
else:
letters.append("0")
return "".join(letters)
genome = 3454579853467L
num_bits = 42
bitmask = 0
for i in range(num_bits):
if random.random() < 0.1:
bitmask += 1L<<i
# genome bit, bitmask -> new value for genome
# if the bitmask is 0, don't change anything
# if it is 1, invert the value
# 0 0 -> 0
# 1 0 -> 1
# 0 1 -> 1
# 1 1 -> 0
# This is an xor
new_genome = (genome ^ bitmask)
print toLSBBinary(genome, num_bits)
print toLSBBinary(bitmask, num_bits)
print toLSBBinary(new_genome, num_bits)
Here's the output of the above
110110010001001010000000101010100010010011
100000101110100000000000000000000000010000
010110111111101010000000101010100010000011
Andrew da***@dalkescientific.com
Matthew Wilson <mw*****@sarcastic-horse.com> wrote in message news:<sl********************@frank.homelinux.net>. .. I'm playing around with genetic algorithms and I want to write a function that mutates an integer by iterating across the bits, and about 1 in 10 times, it should switch a zero to a one, or a one to a zero.
I'm not sure how many bits are inside a python integer. The library reference says at least 32.
It can vary from system to system, and is designed to accomodate
growth. Use sys.maxint to find out how large an integer is on your
system.
I'm thinking about writing a function that eats integers and poops out lists of bools; and then I can iterate through that, and change values in there. But before I do that, does anyone have a better idea?
Using your approach, you would first need to disassemble the integer,
then reassemble it. You can cut this bitwise cranking in half.
Define an integer, in which 10% of the bits is a "1". Then do an
exclusive-or operation between this integer and the one you wish to
mutate. http://www.python.org/cgi-bin/moinmoin/BitwiseOperators
--
John J. Ladasky Jr., Ph.D.
Department of Biology
Johns Hopkins University
Baltimore MD 21218
USA
Earth
"Diez B. Roggisch" <de************@web.de> wrote in message
news:bn*************@news.t-online.com... I'm thinking about writing a function that eats integers and poops out lists of bools; and then I can iterate through that, and change values in there. But before I do that, does anyone have a better idea?
For speed, you should use shift and boolean ops - like this:
def mutate(seq, n=32, prob=0.05): for bit in xrange(n): if random.random() <= prob: seq ^= 1 << bit return seq
Regards,
Diez
And you might want to make a list of precalculated masks using the shift
operator for even more speed.
#! /usr/bin/env python
import sys
print sys.maxint
i = sys.maxint
bitcount = 0
while (i != 0):
i >>= 1
bitcount += 1
print "i = %d" % (i)
print "bitcount = %d" % (bitcount)
masklist = []
for i in range(bitcount):
masklist.append(1 << i)
masklist.append(sys.maxint + 1)
for i in masklist:
print hex(i)
thelist = [0x7F, 0x5A5A5A5A]
for i in thelist:
for mask in masklist:
if ((i & mask) <> 0):
# do True thing
print "True"
else:
# do False thing
print "False"
Matthew Wilson wrote: I'm playing around with genetic algorithms and I want to write a function that mutates an integer by iterating across the bits, and about 1 in 10 times, it should switch a zero to a one, or a one to a zero.
I'm not sure how many bits are inside a python integer. The library reference says at least 32.
I'm thinking about writing a function that eats integers and poops out lists of bools; and then I can iterate through that, and change values in there. But before I do that, does anyone have a better idea?
You may be interested in the 'intbv' class that is part of my 'myhdl'
package for hardware design (link: see signature).
An intbv behaves like a Python long with an indefinite number of bits.
However, it is a mutable type that can also be used as a bitvector
through an indexing and slicing interface. Warning: slicing ranges are
downward as is common in hardware design but uncommon in Python.
Demo: from myhdl import intbv n = intbv(0xDE) n[:8] = 0xFA hex(n)
'0xFADEL' n[8:] = 0xB4 hex(n)
'0xFAB4L' for bit in n[12:8]:
.... print bit
....
1
0
1
0 n[123]
intbv(0L) n[123] = 1 hex(n)
'0x800000000000000000000000000FAB4L'
Regards, Jan
--
Jan Decaluwe - Resources bvba - http://jandecaluwe.com
Losbergenlaan 16, B-3010 Leuven, Belgium
Bored with EDA the way it is? Check this: http://jandecaluwe.com/Tools/MyHDL/Overview.html la*****@my-deja.com (John Ladasky) wrote: I'm thinking about writing a function that eats integers and poops out lists of bools; and then I can iterate through that, and change values in there. But before I do that, does anyone have a better idea?
Using your approach, you would first need to disassemble the integer, then reassemble it. You can cut this bitwise cranking in half. Define an integer, in which 10% of the bits is a "1". Then do an exclusive-or operation between this integer and the one you wish to mutate.
This creates a new problem which is interesting in itself. How to
create this integer? One idea is to first choose *how many* bits are
"1" and next randomly choose from one of the possible placements of
these bits inside an integer. Below I'm computing the probability
distribution for the number of bits that are set.
Anton
def noverk(n, k):
result = 1l
for i in range(k):
result = result *(n - i) / (i + 1)
return result
def test():
prob = 1/10.0
n_bits = 32
chances = [0.0 for i in range(n_bits+1)]
for i in range(n_bits+1):
a = noverk(n_bits,i)
chances[i] = a*(prob**i)*(1-prob)**(n_bits-i)
print "Probability of the number of bits set:\n"
for i,c in enumerate(chances):
print "%i: %e" %(i,c)
if __name__=='__main__':
test()
Anton Vredegoor wrote: la*****@my-deja.com (John Ladasky) wrote:
I'm thinking about writing a function that eats integers and poops out lists of bools; and then I can iterate through that, and change values in there. But before I do that, does anyone have a better idea?
Using your approach, you would first need to disassemble the integer, then reassemble it. You can cut this bitwise cranking in half. Define an integer, in which 10% of the bits is a "1". Then do an exclusive-or operation between this integer and the one you wish to mutate.
This creates a new problem which is interesting in itself. How to create this integer?
I would think the simplest approach is (similar to a suggestion
already made about the original problem) to predefine a set of bitmasks,
each with only one bit set, then simply select one or more at random
and add (or OR) them together, then XOR the result with the original.
You could either iterate over the list of bitmasks, checking a
random result at each step to decide whether to include that bitmask,
or you could just random.shuffle() the list, then select a random
number of entries from the start of the list. Using the new sum()
(or a filter() with operator.add) would make the whole thing as
simple as a couple of function calls:
genome = 12345678
numMutations = random.randint(0, 4)
mutant = genome ^ sum(random.shuffle(bitmasks)[:numMutations])
# done!!
The algorithm used to select the number of mutations to make could
of course be more sophisticated than the above...
-Peter
Brian Kelley <bk*****@wi.mit.edu> wrote: Paul Rubin wrote: Long ints can have as many bits as you want.
Such as -1L which has an infinite number of bits.
Oh come on, that's just silly. If that were true, I could not type this at
a Python prompt because it would cause an overflow:
i = -1L
-1L, in fact, has exactly the same number of bits as 1L and, probably,
1048576L.
--
- Tim Roberts, ti**@probo.com
Providenza & Boekelheide, Inc.
Tim Roberts wrote: Brian Kelley <bk*****@wi.mit.edu> wrote:
Paul Rubin wrote:
Long ints can have as many bits as you want.
Such as -1L which has an infinite number of bits.
Oh come on, that's just silly. If that were true, I could not type this at a Python prompt because it would cause an overflow:
i = -1L
try
i = -1L
while i:
i = i >> 1
and then repeat the statement :) My only point is that you have to be
careful with long ints. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Patrick von Harsdorf |
last post by:
I want to iterate over a collection and delete all unwanted entries.
for item in collection:
del item
of course doesn´t do anything useful. Two things come to mind:
a) iterating backwards...
|
by: Fernando Rodríguez |
last post by:
Hi,
While iterating through a list I'd like to know not just the current element,
but also its index. Is there a better way than this:
i = 0
newList =
for element in aList:...
|
by: ischenko |
last post by:
Hi,
I'm trying to find all modules that contain doctests and execute them
(using DocTestSuite). The problem is how to iterate (programmatically)
through the package's modules.
>>> import M...
|
by: Paxton |
last post by:
At the risk of being told "If it ain't broke, don't fix it", my code works,
but is ugly.
Part of the admin site I'm working on at the moment includes a facility for
users to enter Formulations...
|
by: jose luis fernandez diaz |
last post by:
Hi,
Is this right any stl container (vector, deque, list, . . .)?
typedef vector container;
int main()
{
container<int> c1;
|
by: Dave Hansen |
last post by:
OK, first, I don't often have the time to read this group, so
apologies if this is a FAQ, though I couldn't find anything at
python.org.
Second, this isn't my code. I wouldn't do this. But a...
|
by: Gustaf Liljegren |
last post by:
I ran into this problem today: I got an array with Account objects. I need
to iterate through this array to supplement the accounts in the array with
more data. But the compiler complains when I...
|
by: Nick |
last post by:
Hi all,
Just a quick question. I have a class that exposes a number of fields (which
are themselves custom types) through public properties.
At run time, I have an object whom I'd like to...
|
by: Alan |
last post by:
I was wondering whether it is good programming practice or asking
for trouble to modify a vector while iterating through it. That is, I
want to do something like the following pseudocode in C++:
...
|
by: SBMpy |
last post by:
Instead of itereating through my half-million plus records, I'm looking for a way to query the records and return a subset of records.
Q: Does dbfpy have that functionality?
Q: Or is there a...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
| |