From: Ravi D. <rd...@gm...> - 2011-08-28 00:33:50
|
Hello all, I'm programming a genetic algorithm, and am having difficulties with the hash-tables. The following is the code and a snippet of the output. --- (defun crossover (length-of-chromosome size-of-population hash-of-population) "Take a pruned hash-table. Effect crossover. The resulting hash does not have to be full-sized." (format t "~&Size of pruned population : ~A" (hash-table-count hash-of-population)) (let* ((vector-of-parents (make-array (hash-table-count hash-of-population) :initial-contents (loop for k being the hash-keys in hash-of-population collect k))) ;Easy to access vector of keys (new-hash (make-hash-table :test 'equalp))) (loop for k being the hash-keys in hash-of-population using (hash-value v) do (setf (gethash k new-hash) v)) (loop repeat 20 ;Should find some way of making this not arbitrary, but also leave some space for mutations. for i = (random (length vector-of-parents)) then (random (length vector-of-parents)) and j = (random (length vector-of-parents)) then (random (length vector-of-parents)) and crossover-point = (random length-of-chromosome) then (random length-of-chromosome) with first-parent = () and second-parent = () while (< (hash-table-count new-hash) size-of-population) finally (let ((return-list (loop for k being the hash-keys in new-hash collect k))) (format t "~&Crossover returns list: ~A" return-list) (return new-hash)) do (setf first-parent (aref vector-of-parents i) second-parent (aref vector-of-parents j)) ;Pick 2 to make parents off (rotatef (subseq first-parent crossover-point) (subseq second-parent crossover-point)) (setf (gethash first-parent new-hash) 1 (gethash second-parent new-hash) 1) ))) Crossover returns list: ((1 0 0 0 1 1 1) (1 0 1 0 1 0 1) (0 1 0 1 0 0 0) (1 1 0 1 1 1 0) (1 0 0 1 1 0 0) (1 1 0 1 0 0 0) (1 0 0 1 0 1 0) (1 1 0 1 1 1 0) (1 0 0 0 1 1 1) (1 0 1 0 1 0 1) (1 0 0 1 0 1 0)) ------ As one can see, the list '(1 0 0 0 1 1 1) occurs 2 times. I've made the NEW-HASH hash-table using :test 'EQUAL as well as 'EQUALP, and I get similar results. I was earlier using only the CHROMOSOME-HASH hash-table with the same results, and then decided to see if I was getting the same thing if I created a new hash-table, hence NEW-HASH. I don't know what is going on. I thought that if you do a SETF and GETHASH on an existing key, then you just change the value. If you are not dealing with the value, as I am in this function, then nothing should happen. Only unique keys (chromosomes, in the case of this function) should be added to the hash-table. Am I missing something? Please let me know if I'm doing something wrong here. I'm using sbcl 1.0.50 in archlinux 64-bit. Thank you |
From: Stig H. <sti...@gm...> - 2011-08-28 02:19:32
|
The problem line here is (rotatef (subseq first-parent crossover-point) (subseq second-parent crossover-point)) Here you change the hash keys after adding them to the hash. Not nice. Compare: (defun dont-try-this-at-home () (let ((k1 (list 1))(k2 (list 0)) (hash (make-hash-table :test 'equal))) (setf (gethash k1 hash) 1) (setf (gethash k2 hash) 1) (setf (first k1) 0) (loop for k being the hash-keys in hash collect k))) DONT-TRY-THIS-AT-HOME * (dont-try-this-at-home) ((0) (0)) * Stig Hemmer |
From: Ravi D. <rd...@gm...> - 2011-08-28 11:55:29
|
Thank you, Kevin Reid and Stig Hemmer, So first-parent and second-parent are pointers to the actual keys of the hash-table, and not copies of the elements of the vector, which is in turn a copy of the keys? How do I make this not happen? I tried googling pointers in CL but couldn't find anything. The closest thing I can come up with is to use COPY-LIST on the collected keys when making the vector. I'd still like to learn more about when CL makes a copy and when it works as a pointer. Thank you |
From: Stig H. <sti...@gm...> - 2011-08-28 13:38:48
|
As a general rule of thumb, in CL everything is a pointer (or reference, if you prefer that word), and copies are only made when asked for. COPY-LIST is one way of requesting a copy. You might also be interested in APPEND. If you read the Hyperspec (Ask Google for "Common Lisp Hyperspec") it is very clear on what is copied when. The Hyperspec is a bit dense for a beginner to the language, but it is so wonderfully precise that it should be your first source of information for all things Common Lisp. I am a bit vary of giving you more exact advice as it is not clear to me what your code is trying to do. Stig Hemmer On 8/28/11, Ravi Desai <rd...@gm...> wrote: > Thank you, Kevin Reid and Stig Hemmer, > > So first-parent and second-parent are pointers to the actual keys of the > hash-table, and not copies of the elements of the vector, which is in > turn a copy of the keys? > > How do I make this not happen? I tried googling pointers in CL but > couldn't find anything. The closest thing I can come up with is to use > COPY-LIST on the collected keys when making the vector. I'd still like > to learn more about when CL makes a copy and when it works as a pointer. > > Thank you > > ------------------------------------------------------------------------------ > EMC VNX: the world's simplest storage, starting under $10K > The only unified storage solution that offers unified management > Up to 160% more powerful than alternatives and 25% more efficient. > Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev > _______________________________________________ > Sbcl-help mailing list > Sbc...@li... > https://lists.sourceforge.net/lists/listinfo/sbcl-help > |
From: Ravi D. <rd...@gm...> - 2011-08-28 20:12:18
|
On 08/28/2011 01:38 PM, Stig Hemmer wrote: > As a general rule of thumb, in CL everything is a pointer (or > reference, if you prefer that word), and copies are only made when > asked for. Thanks for the tip. I'll keep it in mind from now on. > COPY-LIST is one way of requesting a copy. You might also be > interested in APPEND. > > If you read the Hyperspec (Ask Google for "Common Lisp Hyperspec") it > is very clear on what is copied when. The Hyperspec is a bit dense > for a beginner to the language, but it is so wonderfully precise that > it should be your first source of information for all things Common > Lisp. > > I am a bit vary of giving you more exact advice as it is not clear to > me what your code is trying to do. The point of this function is to create different permutations (As represented by the list of 0s and 1s). I'm using a hash-table to make sure that each permutation is unique. The permutations are the keys because the hash-table will ensure that they are only unique permutations in that set. Basically, I want to create a set of unique permutations of 1s and 0s. I suppose I could also just use a list instead of a hash-table and use functions like MEMBER, PUSHNEW, etc. Thanks |