## Genetic algorithms

Discussion of Common Lisp
Domus123
Posts: 12
Joined: Fri Oct 02, 2015 1:29 pm

### Genetic algorithms

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 .

David Mullen
Posts: 78
Joined: Mon Dec 01, 2014 12:29 pm
Contact:

### Re: Genetic algorithms

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.

sylwester
Posts: 133
Joined: Mon Jul 11, 2011 2:53 pm

### Re: Genetic algorithms

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)))))
``````
I'm the author of two useless languages that uses BF as target machine.
Currently I'm planning a Scheme compiler :p

Domus123
Posts: 12
Joined: Fri Oct 02, 2015 1:29 pm

### Re: Genetic algorithms

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?

David Mullen
Posts: 78
Joined: Mon Dec 01, 2014 12:29 pm
Contact:

### Re: Genetic algorithms

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)))``````

pjstirling
Posts: 166
Joined: Sun Nov 28, 2010 4:21 pm

### Re: Genetic algorithms

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.