程序设计语言

Bash scripting Tutorial

1

This bash script tutorial assumes no previous knowledge of bash scripting.As you will soon discover in this quick comprehensive bash scripting guide, learning the bash shell scripting is very easy task. Lets begin this bash scripting tutorial with a simple "Hello World" script. Let’s start with Learning the bash Shell: Unix Shell Programming

1. Hello World Bash Shell Script

First you need to find out where is your bash interpreter located. Enter the following into your command line:

1
$ which bash

bash interpreter 
location: /bin/bash

Open up you favorite text editor and a create file called hello_world.sh. Insert the following lines to a file:

NOTE:Every bash shell script in this tutorial starts with shebang:"#!" which is not read as a comment. First line is also a place where you put your interpreter which is in this case: /bin/bash.

Here is our first bash shell script example:

1
2
3
4
5
#!/bin/bash
# declare STRING variable
STRING="Hello World"
#print variable on a screen
echo $STRING

Navigate to a directory where your hello_world.sh is located and make the file executable:

1
$ chmod +x hello_world.sh

Make bash shell 
script executable

Now you are ready to execute your first bash script:

1
./hello_world.sh

Example of simple bash shell 
script

2. Simple Backup bash shell script

1
2
#!/bin/bash
tar -czf myhome_directory.tar.gz /home/linuxconfig

Simple 
Backup bash script

3. Variables

In this example we declare simple bash variable and print it on the screen ( stdout ) with echo command.

1
2
3
#!/bin/bash
 STRING="HELLO WORLD!!!"
 echo $STRING

Bash 
string Variables in bash script

Your backup script and variables:

1
2
3
#!/bin/bash
 OF=myhome_directory_$(date +%Y%m%d).tar.gz
 tar -czf $OF /home/linuxconfig

Bash 
backup Script with bash Variables

3.1. Global vs. Local variables

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/bin/bash
#Define bash global variable
#This variable is global and can be used anywhere in this bash script
VAR="global variable"
function bash {
#Define bash local variable
#This variable is local to bash function only
local VAR="local variable"
echo $VAR
}
echo $VAR
bash
# Note the bash global variable did not change
# "local" is bash reserved word
echo $VAR

Global vs. Local Bash variables in bash script

4. Passing arguments to the bash script

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/bin/bash
#Define bash global variable
#This variable is global and can be used anywhere in this bash script
VAR="global variable"
function bash {
#Define bash local variable
#This variable is local to bash function only
local VAR="local variable"
echo $VAR
}
echo $VAR
bash
# Note the bash global variable did not change
# "local" is bash reserved word
echo $VAR
1
/arguments.sh Bash Scripting Tutorial

Passing 
arguments to the bash script

5. Executing shell commands with bash

1
2
3
4
5
#!/bin/bash
# use backticks " ` ` " to execute shell command
echo `uname -o`
# executing bash command without backticks
echo uname -o

Executing shell commands with bash

6. Reading User Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/bin/bash
 
echo -e "Hi, please type the word: \c "
read  word
echo "The word you entered is: $word"
echo -e "Can you please enter two words? "
read word1 word2
echo "Here is your input: \"$word1\" \"$word2\""
echo -e "How do you feel about bash scripting? "
# read command now stores a reply into the default build-in variable $REPLY
read
echo "You said $REPLY, I'm glad to hear that! "
echo -e "What are your favorite colours ? "
# -a makes read command to read into an array
read -a colours
echo "My favorite colours are also ${colours[0]}, ${colours[1]} and ${colours[2]}:-)"

Reading User 
Input with bash

7. Bash Trap Command

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/bin/bash
# bash trap command
trap bashtrap INT
# bash clear screen command
clear;
# bash trap function is executed when CTRL-C is pressed:
# bash prints message => Executing bash trap subrutine !
bashtrap()
{
    echo "CTRL+C Detected !...executing bash trap !"
}
# for loop from 1/10 to 10/10
for a in `seq 1 10`; do
    echo "$a/10 to Exit." 
    sleep 1;
done
echo "Exit Bash Trap Example!!!"

8. Arrays

8.1. Declare simple bash array

1
2
3
4
5
6
7
8
9
10
11
#!/bin/bash
#Declare array with 4 elements
ARRAY=( 'Debian Linux' 'Redhat Linux' Ubuntu Linux )
# get number of elements in the array
ELEMENTS=${#ARRAY[@]}
 
# echo each element in array 
# for loop
for (( i=0;i<$ELEMENTS;i++)); do
    echo ${ARRAY[${i}]}
done

Declare simple bash array

8.2. Read file into bash array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/bin/bash
#Declare array
 declare -a ARRAY
#Open file for reading to array
exec 10
let count=0
 
while read LINE <&10; do
 
    ARRAY[$count]=$LINE
    ((count++))
done
 
echo Number of elements: ${#ARRAY[@]}
# echo array's content
echo ${ARRAY[@]}
# close file 
exec 10>&-

Read file into bash
 array

9. Bash if / else / fi statements

9.1. Simple Bash if/else statement

Please note the spacing inside the [ and ] brackets! Without the spaces, it won’t work!

1
2
3
4
5
6
7
8
9
#!/bin/bash
directory="./BashScripting"
 
# bash check if directory exists
if [ -d $directory ]; then
	echo "Directory exists"
else 
	echo "Directory does not exists"
fi

Bash if else fi 
statement

9.2. Nested if/else

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#!/bin/bash
 
# Declare variable choice and assign value 4
choice=4
# Print to stdout
 echo "1. Bash"
 echo "2. Scripting"
 echo "3. Tutorial"
 echo -n "Please choose a word [1,2 or 3]? "
# Loop while the variable choice is equal 4
# bash while loop
while [ $choice -eq 4 ]; do
 
# read user input
read choice
# bash nested if/else
if [ $choice -eq 1 ] ; then
 
        echo "You have chosen word: Bash"
 
else                   
 
        if [ $choice -eq 2 ] ; then
                 echo "You have chosen word: Scripting"
        else
 
                if [ $choice -eq 3 ] ; then
                        echo "You have chosen word: Tutorial"
                else
                        echo "Please make a choice between 1-3 !"
                        echo "1. Bash"
                        echo "2. Scripting"
                        echo "3. Tutorial"
                        echo -n "Please choose a word [1,2 or 3]? "
                        choice=4
                fi   
        fi
fi
done

Nested Bash if
 else statement

10. Bash Comparisons

10.1. Arithmetic Comparisons

-lt <
-gt >
-le <=
-ge >=
-eq ==
-ne !=

 

1
2
3
4
5
6
7
8
9
#!/bin/bash
# declare integers
NUM1=2
NUM2=2
if [ $NUM1 -eq $NUM2 ]; then
	echo "Both Values are equal"
else 
	echo "Values are NOT equal"
fi

Bash 
Arithmetic Comparisons

1
2
3
4
5
6
7
8
9
10
#
#!/bin/bash
# declare integers
NUM1=2
NUM2=1
if [ $NUM1 -eq $NUM2 ]; then
	echo "Both Values are equal"
else 
	echo "Values are NOT equal"
fi

Bash 
Arithmetic Comparisons - values are NOT equal

1
2
3
4
5
6
7
8
9
10
11
#!/bin/bash
# declare integers
NUM1=2
NUM2=1
if   [ $NUM1 -eq $NUM2 ]; then
	echo "Both Values are equal"
elif [ $NUM1 -gt $NUM2 ]; then
	echo "NUM1 is greater then NUM2"
else 
	echo "NUM2 is greater then NUM1"
fi

Bash Arithmetic Comparisons - greater then

10.2. String Comparisons

= equal
!= not equal
< less then
> greater then
-n s1 string s1 is not empty
-z s1 string s1 is empty

 

1
2
3
4
5
6
7
8
9
10
#!/bin/bash
#Declare string S1
S1="Bash"
#Declare string S2
S2="Scripting"
if [ $S1 = $S2 ]; then
	echo "Both Strings are equal"
else 
	echo "Strings are NOT equal"
fi

Bash String Comparisons - values are NOT equal

1
2
3
4
5
6
7
8
9
10
#!/bin/bash
#Declare string S1
S1="Bash"
#Declare string S2
S2="Bash"
if [ $S1 = $S2 ]; then
	echo "Both Strings are equal"
else 
	echo "Strings are NOT equal"
fi

bash 
interpreter location: /bin/bash

11. Bash File Testing

-b filename Block special file
-c filename Special character file
-d directoryname Check for directory existence
-e filename Check for file existence
-f filename Check for regular file existence not a directory
-G filename Check if file exists and is owned by effective group ID.
-g filename true if file exists and is set-group-id.
-k filename Sticky bit
-L filename Symbolic link
-O filename True if file exists and is owned by the effective user id.
-r filename Check if file is a readable
-S filename Check if file is socket
-s filename Check if file is nonzero size
-u filename Check if file set-ser-id bit is set
-w filename Check if file is writable
-x filename Check if file is executable

 

1
2
3
4
5
6
7
#!/bin/bash
file="./file"
if [ -e $file ]; then
	echo "File exists"
else 
	echo "File does not exists"
fi

Bash 
File Testing - File does not exist Bash File 
Testing - File exists

Similarly for example we can use while loop to check if file does not exists. This script will sleep until file does exists. Note bash negator "!" which negates the -e option.

1
2
3
4
5
6
#!/bin/bash
 
while [ ! -e myfile ]; do
# Sleep until file does exists/is created
sleep 1
done

12. Loops

12.1. Bash for loop

1
2
3
4
5
6
#!/bin/bash
 
# bash for loop
for f in $( ls /var/ ); do
	echo $f
done

Running for loop from bash shell command line:

1
$ for f in $( ls /var/ ); do echo $f; done

Bash for loop

12.2. Bash while loop

1
2
3
4
5
6
7
#!/bin/bash
COUNT=6
# bash while loop
while [ $COUNT -gt 0 ]; do
	echo Value of count is: $COUNT
	let COUNT=COUNT-1
done

Bash while loop

12.3. Bash until loop

1
2
3
4
5
6
7
#!/bin/bash
COUNT=0
# bash until loop
until [ $COUNT -gt 5 ]; do
        echo Value of count is: $COUNT
        let COUNT=COUNT+1
done

Bash until loop

12.4. Control bash loop with

Here is a example of while loop controlled by standard input. Until the redirection chain from STDOUT to STDIN to the read command exists the while loop continues.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/bin/bash
# This bash script will locate and replace spaces
# in the filenames
DIR="."
# Controlling a loop with bash read command by redirecting STDOUT as
# a STDIN to while loop
# find will not truncate filenames containing spaces
find $DIR -type f | while read file; do
# using POSIX class [:space:] to find space in the filename
if [[ "$file" = *[[:space:]]* ]]; then
# substitute space with "_" character and consequently rename the file
mv "$file" `echo $file | tr ' ' '_'`
fi;
# end of while loop
done

Bash script 
to replace spaces in the filenames with _

13. Bash Functions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
!/bin/bash
# BASH FUNCTIONS CAN BE DECLARED IN ANY ORDER
function function_B {
        echo Function B.
}
function function_A {
        echo $1
}
function function_D {
        echo Function D.
}
function function_C {
        echo $1
}
# FUNCTION CALLS
# Pass parameter to function A
function_A "Function A."
function_B
# Pass parameter to function C
function_C "Function C."
function_D

Bash Functions

14. Bash Select

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/bin/bash
 
PS3='Choose one word: ' 
 
# bash select
select word in "linux" "bash" "scripting" "tutorial" 
do
  echo "The word you have selected is: $word"
# Break, otherwise endless loop
  break  
done
 
exit 0

Bash Select

15. Case statement conditional

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/bin/bash
echo "What is your preferred programming / scripting language"
echo "1) bash"
echo "2) perl"
echo "3) phyton"
echo "4) c++"
echo "5) I do not know !"
read case;
#simple case bash structure
# note in this case $case is variable and does not have to
# be named case this is just an example
case $case in
    1) echo "You selected bash";;
    2) echo "You selected perl";;
    3) echo "You selected phyton";;
    4) echo "You selected c++";;
    5) exit
esac

bash case statement 
conditiona

16. Bash quotes and quotations

Quotations and quotes are important part of bash and bash scripting. Here are some bash quotes and quotations basics.

16.1. Escaping Meta characters

Before we start with quotes and quotations we should know something about escaping meta characters. Escaping will suppress a special meaning of meta characters and therefore meta characters will be read by bash literally. To do this we need to use backslash "\" character. Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/bin/bash
 
#Declare bash string variable
BASH_VAR="Bash Script"
 
# echo variable BASH_VAR
echo $BASH_VAR
 
#when meta character such us "$" is escaped with "\" it will be read literally
echo \$BASH_VAR 
 
# backslash has also special meaning and it can be suppressed with yet another "\"
echo "\\"

escaping meta characters in 
bash

16.2. Single quotes

Single quotes in bash will suppress special meaning of every meta characters. Therefore meta characters will be read literally. It is not possible to use another single quote within two single quotes not even if the single quote is escaped by backslash.

1
2
3
4
5
6
7
8
9
10
#!/bin/bash
 
 #Declare bash string variable
 BASH_VAR="Bash Script"
 
 # echo variable BASH_VAR
 echo $BASH_VAR
 
 # meta characters special meaning in bash is suppressed when  using single quotes 
 echo '$BASH_VAR  "$BASH_VAR"'

Using single quotes in 
bash

16.3. Double Quotes

Double quotes in bash will suppress special meaning of every meta characters except "$", "\" and "`". Any other meta characters will be read literally. It is also possible to use single quote within double quotes. If we need to use double quotes within double quotes bash can read them literally when escaping them with "\". Example:

1
2
3
4
5
6
7
8
9
10
11
12
#!/bin/bash
 
#Declare bash string variable
BASH_VAR="Bash Script"
 
# echo variable BASH_VAR
echo $BASH_VAR
 
# meta characters and its special meaning in bash is 
# suppressed when using double quotes except "$", "\" and "`"
 
echo "It's $BASH_VAR  and \"$BASH_VAR\" using backticks: `date`"

Using double quotes in 
bash

16.4. Bash quoting with ANSI-C style

There is also another type of quoting and that is ANSI-C. In this type of quoting characters escaped with "\" will gain special meaning according to the ANSI-C standard.

/a alert (bell) /b backspace
/e an escape character /f form feed
/n newline /r carriage return
/t horizontal tab /v vertical tab
\\ backslash \` single quote
\nnn octal value of characters ( see [http://www.asciitable.com/ ASCII table] ) \xnn hexadecimal value of characters ( see [http://www.asciitable.com/ ASCII table] )

 

The syntax fo ansi-c bash quoting is: $” . Here is an example:

1
2
3
4
5
#!/bin/bash
 
# as a example we have used \n as a new line, \x40 is hex value for @
# and \56 is octal value for .
echo $'web: www.linuxconfig.org\nemail: web\x40linuxconfig\56org'

quoting in bash with ansi-c 
stype

17. Arithmetic Operations

17.1. Bash Addition Calculator Example

1
2
3
4
5
6
7
8
#!/bin/bash
 
let RESULT1=$1+$2
echo $1+$2=$RESULT1 ' -> # let RESULT1=$1+$2'
declare -i RESULT2
RESULT2=$1+$2
echo $1+$2=$RESULT2 ' -> # declare -i RESULT2; RESULT2=$1+$2'
echo $1+$2=$(($1 + $2)) ' -> # $(($1 + $2))'

Bash Addition Calculator

17.2. Bash Arithmetics

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#!/bin/bash
 
echo '### let ###'
# bash addition
let ADDITION=3+5
echo "3 + 5 =" $ADDITION
 
# bash subtraction
let SUBTRACTION=7-8
echo "7 - 8 =" $SUBTRACTION 
 
# bash multiplication
let MULTIPLICATION=5*8
echo "5 * 8 =" $MULTIPLICATION
 
# bash division
let DIVISION=4/2
echo "4 / 2 =" $DIVISION
 
# bash modulus
let MODULUS=9%4
echo "9 % 4 =" $MODULUS
 
# bash power of two
let POWEROFTWO=2**2
echo "2 ^ 2 =" $POWEROFTWO
 
 
echo '### Bash Arithmetic Expansion ###'
# There are two formats for arithmetic expansion: $[ expression ] 
# and $(( expression #)) its your choice which you use
 
echo 4 + 5 = $((4 + 5))
echo 7 - 7 = $[ 7 - 7 ]
echo 4 x 6 = $((3 * 2))
echo 6 / 3 = $((6 / 3))
echo 8 % 7 = $((8 % 7))
echo 2 ^ 8 = $[ 2 ** 8 ]
 
 
echo '### Declare ###'
 
echo -e "Please enter two numbers \c"
# read user input
read num1 num2
declare -i result
result=$num1+$num2
echo "Result is:$result "
 
# bash convert binary number 10001
result=2#10001
echo $result
 
# bash convert octal number 16
result=8#16
echo $result
 
# bash convert hex number 0xE6A
result=16#E6A
echo $result

Bash Arithmetic 
Operations

17.3. Round floating point number

1
2
3
4
5
6
7
8
#!/bin/bash
# get floating point number
floating_point_number=3.3446
echo $floating_point_number
# round floating point number with bash
for bash_rounded_number in $(printf %.0f $floating_point_number); do
echo "Rounded number with bash:" $bash_rounded_number
done

Round 
floating point number with bash

17.4. Bash floating point calculations

1
2
3
4
5
6
7
8
9
10
#!/bin/bash
# Simple linux bash calculator 
echo "Enter input:" 
read userinput
echo "Result with 2 digits after decimal point:"
echo "scale=2; ${userinput}" | bc 
echo "Result with 10 digits after decimal point:"
echo "scale=10; ${userinput}" | bc 
echo "Result as rounded integer:"
echo $userinput | bc

Bash floating point 
calculations

18. Redirections

18.1. STDOUT from bash script to STDERR

1
2
3
#!/bin/bash
 
 echo "Redirect this STDOUT to STDERR" 1>&2

To proof that STDOUT is redirected to STDERR we can redirect script’s output to file:

STDOUT from bash script to 
STDERR

18.2. STDERR from bash script to STDOUT

1
2
3
#!/bin/bash
 
 cat $1 2>&1

To proof that STDERR is redirected to STDOUT we can redirect script’s output to file:

STDERR from bash script to 
STDOUT

18.3. stdout to screen

The simple way to redirect a standard output ( stdout ) is to simply use any command, because by default stdout is automatically redirected to screen.

1
cat /proc/partitions

bash stdout to screen

18.4. stdout to file

Here we use ">" to redirect stdout to a file "partitions.txt".

1
cat /proc/partitions > partitions.txt

bash stdout to file

18.5. stderr to file

In this example you will redirect the standard error ( stderr ) to a file and stdout to a default screen.

1
grep -r hda6 * . 2> stderr.txt

bash stderr to file

18.6. stdout to stderr

In this case the output of a command will be written to the same descriptor as a stderr.

1
grep -r hda6 * . 1>&2 stderr.txt

bash stdout to stderr

18.7. stderr to stdout

In this case the stderr of a command will be written to the same descriptor as a stdout.

1
grep -r hda6 * . 2>&1 stderr.txt

bash stderr to stdout

18.8. stderr and stdout to file

1
grep -r hda6 * . &> stderr_and_stdout.txt

stderr and stdout 
to file

提出一种高精度延迟函数的实现,欢迎交流

0

在Windows系统下,需要延迟一定的时间后继续流程,貌似缺乏这种库函数,MFC提供的延迟函数似乎本质精度无法保证。比如Sleep。在下面提出一种方法,请大家斧正。当然先提出一点,有人认为在Windows系统先不可能获得准确定时,或者把系统挂起来延迟等待不符合多线程编程规范。是的,谢谢您的提醒,但这个讨论中大家就不要再重复这样的观点啦。我们的确需要精确定时,即使我把系统完全占用也在所不惜。不就是几十毫秒嘛 :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// 高精度延迟函数 【开发草稿】 Rev 0.01
/* 注:MSDN中提到的以下问题,本版本程序并未处理!!
On a multiprocessor computer, it should not matter which processor is called. 
However, you can get different results on different processors due to bugs 
in the basic input/output system (BIOS) or the hardware abstraction layer (HAL).
To specify processor affinity for a thread, use the SetThreadAffinityMask function. 
*/
int DelayPrecision(int TimeInMilliSecond)
{
    LARGE_INTEGER Frequency;
    LARGE_INTEGER CountBegin;
    LARGE_INTEGER CountNow;
    LONGLONG DelayCount;
    LONGLONG EndCount;
 
    if (0 != QueryPerformanceFrequency(&Frequency))
    {
        //试算终止计数
        DelayCount = Frequency.QuadPart / 1000 * TimeInMilliSecond;
        if (0 != QueryPerformanceCounter(&CountBegin))
        {
            EndCount = CountBegin.QuadPart + DelayCount;
            if (EndCount < CountBegin.QuadPart)
            {
                //计数器循环回去了
                while (1)
                {
                    if (0 != QueryPerformanceCounter(&CountNow))
                    {
                        if (CountNow.QuadPart < CountBegin.QuadPart && CountNow.QuadPart > EndCount)
                        {
                            return 1;
                        }
                    }
                    else
                    {
                        break;
                    }
                }
            }
            else
            {
                //一般情况
                while (1)
                {
                    if (0 != QueryPerformanceCounter(&CountNow))
                    {
                        if (CountNow.QuadPart > EndCount)
                        {
                            return 2;
                        }
                    }
                    else
                    {
                        break;
                    }
                }
            }
 
        }
 
    }
 
    //如果无法使用高精度定时器,拿Sleep凑合着用吧.
    Sleep(TimeInMilliSecond);
 
 
    return 0;
}

[转载]简单蚁群算法的实现

0

本文转载自http://blog.chinaunix.net/u1/34560/showart_312651.html

引言

蚁群算法(ant colony optimization,ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法。初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。蚁群算法是一种求解组合最优化问题的新型通用启发式方法,该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。正因为蚁群算法有这些优点,很多研究者都在致力研究和改过它,本文的目的正是为了介绍蚁群算法,学习如何编写蚁群算法。

蚁群算法的介绍

昆虫世界中,蚂蚁的组成是一种群居的世袭大家庭,我们称之为蚁群。蚂蚁分为世袭制的蚁王(后)和工蚁两种,它们具有高度组织的社会性,彼此沟通不仅可以借助触觉和视觉的联系,在大规模的协调行动中还可以借助外激素(有些书称信息素)之类的信息介质。

首先我们要理解蚂蚁是如何觅食的,蚂蚁平时在巢穴附近作无规则行走,一量发现食物并不立即进食而是将之搬回蚁穴与其它蚂蚁分享,在食物小时则独自搬回蚁穴,否则就回蚁穴搬兵,一路上会留下外激素,食物越大外激素的浓度就越大,越能吸引其它的蚂蚁过去一起搬去食物,这样最终就能将食物全部搬回蚁穴。这个过程用程序实现看似非常复杂,要编写一个“智能”的蚂蚁也看似不太可能,事实上每个蚂蚁只做了非常简单的工作:检查某个范围内有无食物,并逐渐向外激素浓的方向运动。简而言之,蚁群运动无非是同时反复执行多个简单规则而已。下面详细说明蚁群中的这些简单规则:

1、范围:蚂蚁观察到的范围是一个方格世界,蚂蚁有一个参数为速度半径(一般是3),那么它能观察到的范围就是3*3个方格世界,并且能移动的距离也在这个范围之内。

2、环境:蚂蚁所在的环境是一个虚拟的世界,其中有障碍物,有别的蚂蚁,还有外激素,外激素有两种,一种是找到食物的蚂蚁洒下的食物外激素,一种是找到窝的蚂蚁洒下的窝的外激素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让外激素消失。

3、觅食规则:在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去。否则看是否有外激素,并且比较在能感知的范围内哪一点的外激素最多,这样,它就朝外激素多的地方走,并且每只蚂蚁多会以小概率犯错误,从而并不是往外激素最多的点移动。蚂蚁找窝的规则和上面一样,只不过它对窝的外激素做出反应,而对食物外激素没反应。

4、移动规则: 每只蚂蚁都朝向外激素最多的方向移,并且,当周围没有外激素指引的时候,蚂蚁会按照自己原来运动的方向惯性的运动下去,并且,在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈,它会记住最近刚走过了哪些点,如果发现要走的下一点已经在最近走过了,它就会尽量避开。

5、避障规则:如果蚂蚁要移动的方向有障碍物挡住,它会随机的选择另一个方向,并且有外激素指引的话,它会按照觅食的规则行为。

7、播撒外激素规则:每只蚂蚁在刚找到食物或者窝的时候撒发的外激素最多,并随着它走远的距离,播撒的外激素越来越少。

根据这几条规则,蚂蚁之间并没有直接的关系,但是每只蚂蚁都和环境发生交互,而通过外激素这个纽带,实际上把各个蚂蚁之间关联起来了。比如,当一只蚂蚁找到了食物,它并没有直接告诉其它蚂蚁这儿有食物,而是向环境播撒外激素,当其它的蚂蚁经过它附近的时候,就会感觉到外激素的存在,进而根据外激素的指引找到了食物。成功的觅食算法正是最小化搜索食物的时间。

蚁群算法的实现

理解蚁群算法的实质之后写出一个简单蚁群算法也不是太困难,关键是实现以上介绍的几个规则,下面用JAVA简单讲述一下以上规则的实现。

1、蚂蚁:蚂蚁是蚁群中最小的单位,是所以简单规则应用的最小个体。

 

1
2
3
4
5
6
7
8
9
10
11
12
public class Ant
{
    public Square SQUARE;           //蚂蚁所在方格
    public Food CARRYING = null;    //所搬的食物数
    public int ID;                  //蚂蚁的编号
    public boolean HELPING = false; //是否帮忙搬运食物
 
public void move(int turn)
{
    //蚂蚁移动到下一个方格
}
}

2、范围:蚂蚁所在的方格应该包含附近的方格编号,所含食物数量,蚂蚁数量,外激素的浓度,以及坐标等信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Square
{ public Square NE;            //附近的8个方向的方格
 
     public Square N;
     public Square NW;
     public Square W;
     public Square SW;
     public Square S;
     public Square SE;
     public Square E;
     public LinkedList ANTS;        //本方格中包含的蚂蚁
     public Food FOOD;            //本方格中包含的食物数
     public Nest NEST;                //方格为蚁穴
     public Pheromone_1 PHEROMONE_1;            //本方格中的外激素含量
     public int X;            //本方格的坐标
     public int Y;
     private World WORLD;            //所属的环境
     public boolean WALL;            //是否有障碍物
 
    public Square(int x, int y, World world)
    {
        FOOD = null;
        NEST = null;
        PHEROMONE_1 = null;
        X = x;
        Y = y;
        WORLD = world;
        WALL = false;
        ANTS = new LinkedList();
    }

3、环境:环境是由多个方格组成的,是一个平面的,因此用一个方格的二维数组来表示是最合适不过的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class World
{
    private Square[][] WORLD;        //定义环境二维数组
    private int WIDTH;                //环境的长宽
    private int HEIGHT;
    private Pheromone_1List P1LIST;        //保存所有外激素的列表
 
    public World(Pheromone_1List p1list)
    {
        this.WIDTH = Settings.WIDTH;
        this.HEIGHT = Settings.HEIGHT;
        this.P1LIST = p1list;
        WORLD = new Square[WIDTH][HEIGHT];
    }

     4、觅食规则,移动规则和避障规则:这三种规则全都跟蚂蚁的移动方向有关,并在移动前都要先计算周围方格的外激素浓度,选择外激素浓度最高的方格方向移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private Square chooseBestSquare()
{
     Square[] square_list = {SQUARE.E, SQUARE.NE, SQUARE.N, SQUARE.NW, SQUARE.W, SQUARE.SW, SQUARE.S, SQUARE.SE};
        double current_best_value = 0;
        double value = 0;
        Square square = SQUARE;
        // 选择最好的方格
 
        for(int i=0;i<square_list.length;i++)
        {
            value = calculateSquareValue(square_list[i]);//计算方格值
            if(value > current_best_value)
            {
                current_best_value = value;
                square = square_list[i];
            }
        }
        if(square.ANTS.size() >= Settings.MAXIMUM_NUMBER_OF_ANTS)
        {
          return SQUARE;
        }
        return square;
    }

1
2
3
4
5
6
7
8
9
10
11
12
private double calculateSquareValue(Square s)
{
    double[] thresholds = Settings.THRESHOLDS;
    if(s==null || s.WALL) // 方格有障碍物
    {
        return -100000;
    }
 
    // 计算方格中各项参数的值
    return s.getFood()*thresholds[0]        // 食物
    + s.getPheromone_1() * thresholds[1]    // 外激素
}

5、播撒外激素规则:每只蚂蚁找到食物后会根据食物的数量播撒相应量的外激素,以便其它蚂蚁能够更快得找到这堆食物。

1
2
3
4
5
private void putPheromone_1(double amount)
{
    if(SQUARE.getPheromone_1() < Settings.PHEROMONE_LIMIT)
     SQUARE.addPheromone_1(amount);
}

从以上蚁群算法中各个要素的代码来看,实现蚁群算法并不难。每只蚂蚁并不是像我们想象的需要知道整个环境的信息,它们只关心很小范围内的眼前信息,而且根据这些局部信息利用几条简单的规则进行决策,这样,在蚁群这个集体里,复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律。

蚁群算法的不足

本文实现的蚁群算法只是简单的大致模拟蚁群的觅食过程,真正的蚂蚁觅食过程远比这个复杂,比如增加蚂蚁搬运食物的距离和数量,蚂蚁在搬运食物发现更大的食物可能会丢弃原有食物,还可以增加蚂蚁搬运食物回蚁穴的最短路径的求解。同时需要注意的是,由于蚁群算法觅食的过程,蚁群算法可能会过早的收敛并陷入局部最优解。

Go to Top