Page 1 of 1
Genetic algorithms
Posted: Wed Apr 06, 2016 5:53 pm
by Domus123
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
by David Mullen
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
by sylwester
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
by Domus123
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
by David Mullen
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
by pjstirling
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.