Page 1 of 1

### Genetic algorithms

Posted: Wed Apr 06, 2016 5:53 pm
Hey guys, i'm learning a bit of IA and i want to make a traveling salesman problem using GA .
So i have a doubt , i have some points pre-defined ex:

Code: Select all

``````(defvar a '(23 20))
(defvar b '(10 30))
(defvar c '(0 45))
(defvar d '(43 0))
``````
How can i randomly create a list that contain all of it elements only one time ? I think some ways that wouldn't be very fast .

### Re: Genetic algorithms

Posted: Thu Apr 07, 2016 10:48 am
What are the elements of the list? I imagine a destructive shuffle would be fast enoughâ€”but that's assuming you already have a list for shuffling.

### Re: Genetic algorithms

Posted: Sun Apr 10, 2016 4:25 pm
You can randomize it with sort:

Code: Select all

``````(defparameter *lst* (list a b c d)) ; list of the elements
(setf *lst*
(sort *lst*
(lambda (&rest lst)
(< 0.5 (random 1.0)))))
``````

### Re: Genetic algorithms

Posted: Mon Apr 11, 2016 5:26 pm
sylwester wrote:You can randomize it with sort:

Code: Select all

``````(defparameter *lst* (list a b c d)) ; list of the elements
(setf *lst*
(sort *lst*
(lambda (&rest lst)
(< 0.5 (random 1.0)))))
``````

That code seems work,but how exactly that work?

### Re: Genetic algorithms

Posted: Wed Apr 13, 2016 1:07 pm
Domus123 wrote:
sylwester wrote:You can randomize it with sort:

Code: Select all

``````(defparameter *lst* (list a b c d)) ; list of the elements
(setf *lst*
(sort *lst*
(lambda (&rest lst)
(< 0.5 (random 1.0)))))
``````
That code seems work,but how exactly that work?
It won't work with every sorting algorithm. With something like quicksort, you're partitioning the sequence recursively and rearranging each partition around some pivot elementâ€”with a random predicate, the pivot is irrelevant, of course. So it's like flipping a coin to decide whether to swap around a given element within the partition. Personally, I'd use a Fisher-Yates shuffle, which is like playing Bingo:

Code: Select all

``````(defun shuffle (list)
(loop for tail on list
for n downfrom (list-length list) above 1
do (rotatef (car tail) (nth (random n) tail))
finally (return list)))``````

### Re: Genetic algorithms

Posted: Fri Apr 15, 2016 3:41 pm
I was actually surprised by it too, because the C++ sort is allowed to crash if your items comparison changes between calls. I wouldn't have even thought of doing it this way, but I checked the hyperspec and:
This is guaranteed even if the predicate does not really consistently represent a total order (in which case the elements will be scrambled in some unpredictable way, but no element will be lost)
Since that's exactly what is wanted here using RANDOM with SORT is fine.