生成十个随机目标点并输出位置坐标,再用麻雀搜索算法进行路径规划,要求每个目标点只被访问一次,最后输出最短路径 Python代码
时间: 2024-02-18 08:05:46 浏览: 23
好的,以下是生成随机目标点并输出位置坐标的Python代码:
```python
import random
num_targets = 10
min_coord, max_coord = 0, 100
targets = []
for i in range(num_targets):
x, y = random.randint(min_coord, max_coord), random.randint(min_coord, max_coord)
targets.append((x, y))
print(f"Target {i+1} position: ({x}, {y})")
```
接下来是使用麻雀搜索算法进行路径规划的Python代码:
```python
import math
import copy
def euclidean_distance(coord1, coord2):
x1, y1 = coord1
x2, y2 = coord2
return math.sqrt((x1 - x2)**2 + (y1 - y2)**2)
def calculate_path_length(path, targets):
total_length = 0
for i in range(len(path)-1):
total_length += euclidean_distance(targets[path[i]], targets[path[i+1]])
return total_length
def sparrow_search(num_targets, max_iter=100):
# Initialize population
population = [random.sample(range(num_targets), num_targets) for _ in range(10)]
best_path = copy.deepcopy(population[0])
best_length = calculate_path_length(best_path, targets)
# Main loop
for i in range(max_iter):
# Evaluate fitness
fitness = [1 / calculate_path_length(path, targets) for path in population]
best_index = fitness.index(max(fitness))
if calculate_path_length(population[best_index], targets) < best_length:
best_path = copy.deepcopy(population[best_index])
best_length = calculate_path_length(best_path, targets)
# Select parents for crossover
parents = random.choices(population, weights=fitness, k=2)
# Crossover
child1, child2 = [None] * num_targets, [None] * num_targets
start, end = sorted(random.sample(range(num_targets), 2))
child1[start:end+1] = parents[0][start:end+1]
child2[start:end+1] = parents[1][start:end+1]
for i in range(num_targets):
if child1[i] is None:
j = 0
while parents[1][j] in child1:
j += 1
child1[i] = parents[1][j]
if child2[i] is None:
j = 0
while parents[0][j] in child2:
j += 1
child2[i] = parents[0][j]
# Mutation
if random.random() < 0.1:
i, j = random.sample(range(num_targets), 2)
child1[i], child1[j] = child1[j], child1[i]
if random.random() < 0.1:
i, j = random.sample(range(num_targets), 2)
child2[i], child2[j] = child2[j], child2[i]
# Add children to population
population += [child1, child2]
# Select survivors
fitness = [1 / calculate_path_length(path, targets) for path in population]
sorted_indices = sorted(range(len(fitness)), key=lambda i: fitness[i], reverse=True)
population = [population[i] for i in sorted_indices[:10]]
return best_path, best_length
targets = [(65, 14), (15, 18), (16, 99), (80, 59), (54, 50), (55, 49), (26, 63), (6, 83), (25, 78), (26, 36)]
best_path, best_length = sparrow_search(len(targets))
print(f"Shortest path length: {best_length}")
print("Shortest path: ", end="")
for i in range(len(best_path)):
print(f"{best_path[i]+1}->", end="")
print("1")
```
需要注意的是,这里的目标点位置是手动指定的,如果要使用上面生成的随机目标点,需要将`targets`变量替换成生成的目标点列表。