प्रौद्योगिकी साझेदारी

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. विकास इतिहास

आनुवंशिक एल्गोरिदम् (GA) प्राकृतिकचयनेन आनुवंशिकशास्त्रेण च प्रेरितम् अनुकूलन-एल्गोरिदम् अस्ति । प्रथमवारं अमेरिकनविद्वान् जॉन् हॉलैण्ड् इत्यनेन १९७० तमे दशके प्रस्तावितं, यस्य उद्देश्यं प्राकृतिकप्रणालीषु अनुकूलतायाः अध्ययनं भवति, सङ्गणकविज्ञाने अनुकूलनसमस्यासु च प्रयुक्तम्

प्रमुख विकास इतिहास

• १९७५ तमे वर्षे: जॉन् हॉलैण्ड् इत्यनेन प्रथमवारं "Adaptation in Natural and Artificial Systems" इति पुस्तके आनुवंशिक-एल्गोरिदम् इत्यस्य अवधारणा प्रस्ताविता ।

• १९८० तमे दशके: कार्य-अनुकूलनम्, संयोजनात्मक-अनुकूलनम् इत्यादिषु क्षेत्रेषु आनुवंशिक-एल्गोरिदम्-प्रयोगः आरब्धः, क्रमेण च ध्यानं आकर्षितवान् ।

• १९९० तमे दशके: सङ्गणकगणनाशक्तिसुधारेन अभियांत्रिकी, अर्थशास्त्रं, जीवविज्ञानम् इत्यादिषु क्षेत्रेषु आनुवंशिक-अल्गोरिदम् इत्यस्य व्यापकरूपेण उपयोगः कृतः अस्ति ।

• २००० तमे दशके वर्तमानपर्यन्तम्: आनुवंशिक-अल्गोरिदम्-सिद्धान्तस्य अनुप्रयोगस्य च अग्रे विकासः अभवत्, तथा च विविधाः उन्नत-अल्गोरिदम्-प्रयोगाः उद्भूताः, यथा...遗传编程(आनुवंशिक प्रोग्रामिंग) 、差分进化(विभेदक विकास) इत्यादि।

2. गणितीयसिद्धान्ताः

आनुवंशिक एल्गोरिदम् प्राकृतिकचयनस्य आनुवंशिकशास्त्रस्य च आधारेण यादृच्छिकसन्धानपद्धतिः अस्ति अस्य मूलविचारः जैविकविकासप्रक्रियायाः अनुकरणम् अस्ति ।चिनोतु、अनुप्रस्थतथाउत्परिवर्तनसंचालन, निरन्तरं जनसंख्यानां नूतना पीढी जनयति, तस्मात् क्रमेण इष्टतमसमाधानस्य समीपं गच्छति।

आनुवंशिक एल्गोरिदमस्य मूलभूतपदार्थाः

1. आरम्भीकरणम्: प्रारम्भिकजनसंख्यां यादृच्छिकरूपेण जनयन्तु।

2. चिनोतु: फिटनेस फंक्शन् इत्यस्य आधारेण उत्तमव्यक्तिनां चयनं कुर्वन्तु।

3. अनुप्रस्थ: मातापितृव्यक्तिस्य जीनानां भागस्य आदानप्रदानं कृत्वा नूतनं व्यक्तिं रचयन्तु।

4. उत्परिवर्तन: व्यक्तिस्य केषाञ्चन जीनानां यादृच्छिकरूपेण परिवर्तनं कुर्वन्ति।

5. पुनरावृत्तिः: यावत् समाप्तिशर्तः न पूर्यते तावत् चयनं, क्रॉसओवरं, उत्परिवर्तनप्रक्रियाः पुनः पुनः कुर्वन्तु।

गणितीय वर्णन

कल्पयतु यत् जनसंख्यायाः आकारः N अस्ति तथा च प्रत्येकस्य व्यक्तिस्य गुणसूत्रदीर्घता L अस्ति आनुवंशिक-एल्गोरिदम् इत्यस्य गणितीय-प्रक्रिया निम्नलिखितरूपेण अस्ति ।

1. आरम्भीकरणम्: जनसङ्ख्या जनयतु , यत्र गुणसूत्रः अस्ति।

2. फिटनेस गणना: प्रत्येकस्य व्यक्तिस्य फिटनेस मूल्यस्य गणनां कुर्वन्तु।

3. चिनोतु: फिटनेस-मूल्यानां आधारेण व्यक्तिनां चयनं कुर्वन्तु सामान्यतया प्रयुक्ताः पद्धतयः रूलेट्-चयनम्, टूर्नामेण्ट्-चयनम् इत्यादयः सन्ति ।

4. अनुप्रस्थ: नूतनान् व्यक्तिं जनयितुं क्रॉसओवर-सञ्चालनार्थं केचन व्यक्तिः चयनं कुर्वन्तु।

5. उत्परिवर्तन: उत्परिवर्तितव्यक्तिं जनयितुं केषुचित् नवीनव्यक्तिषु उत्परिवर्तनक्रियाः कुर्वन्तु।

6. जनसंख्या अद्यतन करें: पुरातनव्यक्तिनां स्थाने नूतनव्यक्तिः स्थापयित्वा जनसंख्यायाः नूतनपीढी निर्मातुं शक्यते।

7. समाप्ति शर्त: यदि पूर्वनिर्धारितसमाप्तिस्थितिः (यथा पुनरावृत्तीनां संख्या अथवा फिटनेस-दहलीजः) प्राप्ता भवति तर्हि इष्टतमं समाधानं आउटपुट् भवति ।

3. अनुप्रयोगपरिदृश्यानि

आनुवंशिक-अल्गोरिदम्-इत्यस्य अनुकूलतायाः, दृढतायाः च कारणात् अनेकक्षेत्रेषु व्यापकरूपेण उपयोगः कृतः अस्ति :

अभियांत्रिकी अनुकूलन

• संरचनात्मक अनुकूलन: हल्कं उच्च-शक्तियुक्तं च संरचनां डिजाइनं कुर्वन्तु।

• पैरामीटर अनुकूलन: इष्टतमप्रदर्शनार्थं प्रणालीमापदण्डान् समायोजयन्तु।

अर्थशास्त्र एवं वित्त

• पोर्टफोलियो अनुकूलन: अधिकतमं प्रतिफलं प्राप्तुं निवेशसम्पत्त्याः आवंटनं कुर्वन्तु।

• विपण्य भविष्यवाणी: शेयरमूल्यानां, बाजारस्य प्रवृत्तीनां च पूर्वानुमानं कुर्वन्तु।

जैव सूचना विज्ञान

• जीन अनुक्रम तुलना: DNA अनुक्रमस्य तुलनां विश्लेषणं च कुर्वन्तु।

• प्रोटीन संरचना भविष्यवाणी: प्रोटीनस्य त्रिविमसंरचनायाः पूर्वानुमानं कुर्वन्तु।

यन्त्रशिक्षणम्

• तंत्रिका जाल प्रशिक्षण: तंत्रिकाजालस्य भारस्य संरचनायाः च अनुकूलनं कुर्वन्तु।

• विशेषताचयनम्: वर्गीकरणाय वा प्रतिगमनाय वा ये विशेषताः सर्वाधिकं लाभप्रदाः सन्ति तेषां चयनं कुर्वन्तु।

4. पायथन् उदाहरणानां दृश्यकार्यन्वयनम्

निम्नलिखित कोड उदाहरणं यात्राविक्रेता समस्यायाः समाधानार्थं आनुवंशिक एल्गोरिदम् कार्यान्वितं करोति ।旅行商问题(TSP) एकः क्लासिकः संयोजनात्मकः अनुकूलनसमस्या अस्ति यस्य उद्देश्यं भवति यत् एकस्य यात्रीविक्रेतुः कृते लघुतममार्गं अन्वेष्टुम् यत् सः नगरानां दत्तसमूहे प्रत्येकं नगरं सम्यक् एकवारं भ्रमति अन्ते च आरम्भिकनगरं प्रति प्रत्यागन्तुं, अर्थात् कुलयात्रादूरतां न्यूनीकर्तुं वा व्ययः, रसदशास्त्रे, उत्पादननिर्धारणे इत्यादिषु क्षेत्रेषु व्यापकरूपेण प्रयुक्तः ।

वयं प्रथमं चीनदेशस्य सर्वाणि प्रान्तीयराजधानीनगराणि (सहितं...चीनदेशस्य ताइवानप्रान्तस्य राजधानी ताइपे) तथा तस्य समन्वयदत्तांशः, तथा च उपयोगः哈夫曼公式द्वयोः बिन्दुयोः मध्ये दूरं गणयित्वा ततः उत्तीर्णं कुर्वन्तु遗传算法प्रारम्भिकजनसंख्यां निर्माय, पुनरुत्पादनं, उत्परिवर्तनं, अग्रिमपीढीं जनयतु, मार्गस्य निरन्तरं अनुकूलनं कुर्वन्तु, अन्ते च प्रत्येकस्मिन् पीढौ लघुतममार्गस्य दूरं तदनुरूपमार्गं च अभिलेखयन्तु, सर्वेषु पुनरावृत्तौ लघुतमं मार्गं अन्विष्य नक्शे दृग्गतरूपेण प्रदर्शयन्तुसर्वाणि नगरस्थानानि、पुनरावृत्तीनां संख्यायाः सह फिटनेसः परिवर्तते इष्टतममार्गस्य सङ्गमेन अन्तिमपरिणामे चोङ्गकिङ्ग्-नगरात् सर्वेषु नगरेषु लघुतमः मार्गः तस्य कुलदूरता च दर्शयति । कुलम् द्वौ प्रशिक्षणौ कृतौ प्रथमः पुनरावृत्तिसङ्ख्या २००० आसीत् तथा च चलनस्य समयः २०००० इति निर्धारितः आसीत् तथा च चालनसमयः प्रायः १५ निमेषाः आसीत् ।

एकस्मिन् वाक्ये सारांशतः : चोङ्गकिङ्ग्-नगरात् आरभ्य चीनदेशस्य सर्वेषु प्रान्तीयराजधानीनगरेषु यात्रां कुर्वन्तु, लघुतममार्गं अन्वेष्टुं आनुवंशिक-एल्गोरिदम्-प्रयोगं कुर्वन्तु । निम्नलिखितम् अस्ति कोड कार्यान्वयनम् :

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.basemap import Basemap
import random
from math import radians, sin, cos, sqrt, atan2
 
# 设置随机种子以保证结果可重复
random.seed(42)
np.random.seed(42)
 
# 定义城市和坐标列表，包括台北
cities = {
    "北京": (39.9042, 116.4074),
    "天津": (39.3434, 117.3616),
    "石家庄": (38.0428, 114.5149),
    "太原": (37.8706, 112.5489),
    "呼和浩特": (40.8426, 111.7511),
    "沈阳": (41.8057, 123.4315),
    "长春": (43.8171, 125.3235),
    "哈尔滨": (45.8038, 126.5349),
    "上海": (31.2304, 121.4737),
    "南京": (32.0603, 118.7969),
    "杭州": (30.2741, 120.1551),
    "合肥": (31.8206, 117.2272),
    "福州": (26.0745, 119.2965),
    "南昌": (28.6820, 115.8579),
    "济南": (36.6512, 117.1201),
    "郑州": (34.7466, 113.6254),
    "武汉": (30.5928, 114.3055),
    "长沙": (28.2282, 112.9388),
    "广州": (23.1291, 113.2644),
    "南宁": (22.8170, 108.3665),
    "海口": (20.0174, 110.3492),
    "重庆": (29.5638, 106.5507),
    "成都": (30.5728, 104.0668),
    "贵阳": (26.6477, 106.6302),
    "昆明": (25.0460, 102.7097),
    "拉萨": (29.6520, 91.1721),
    "西安": (34.3416, 108.9398),
    "兰州": (36.0611, 103.8343),
    "西宁": (36.6171, 101.7782),
    "银川": (38.4872, 106.2309),
    "乌鲁木齐": (43.8256, 87.6168),
    "台北": (25.032969, 121.565418)
}
 
# 城市列表和坐标
city_names = list(cities.keys())
locations = np.array(list(cities.values()))
chongqing_index = city_names.index("重庆")
 
# 使用哈夫曼公式计算两点间的距离
def haversine(lat1, lon1, lat2, lon2):
    R = 6371.0  # 地球半径，单位为公里
    dlat = radians(lat2 - lat1)
    dlon = radians(lon1 - lon2)
    a = sin(dlat / 2)**2 + cos(radians(lat1)) * cos(radians(lat2)) * sin(dlon / 2)**2
    c = 2 * atan2(sqrt(a), sqrt(1 - a))
    distance = R * c
    return distance
 
# 计算路径总距离的函数，单位为公里
def calculate_distance(path):
    return sum(haversine(locations[path[i]][0], locations[path[i]][1], locations[path[i + 1]][0], locations[path[i + 1]][1]) for i in range(len(path) - 1))
 
# 创建初始种群
def create_initial_population(size, num_cities):
    population = []
    for _ in range(size):
        individual = random.sample(range(num_cities), num_cities)
        # 确保重庆为起点
        individual.remove(chongqing_index)
        individual.insert(0, chongqing_index)
        population.append(individual)
    return population
 
# 对种群进行排名
def rank_population(population):
    # 按照路径总距离对种群进行排序
    return sorted([(i, calculate_distance(individual)) for i, individual in enumerate(population)], key=lambda x: x[1])
 
# 选择交配池
def select_mating_pool(population, ranked_pop, elite_size):
    # 选择排名前elite_size的个体作为交配池
    return [population[ranked_pop[i][0]] for i in range(elite_size)]
 
# 繁殖新个体
def breed(parent1, parent2):
    # 繁殖两个父母生成新个体
    geneA = int(random.random() * (len(parent1) - 1)) + 1
    geneB = int(random.random() * (len(parent1) - 1)) + 1
    start_gene = min(geneA, geneB)
    end_gene = max(geneA, geneB)
    child = parent1[:start_gene] + parent2[start_gene:end_gene] + parent1[end_gene:]
    child = list(dict.fromkeys(child))
    missing = set(range(len(parent1))) - set(child)
    for m in missing:
        child.append(m)
    # 确保重庆为起点
    child.remove(chongqing_index)
    child.insert(0, chongqing_index)
    return child
 
# 突变个体
def mutate(individual, mutation_rate):
    for swapped in range(1, len(individual) - 1):
        if random.random() < mutation_rate:
            swap_with = int(random.random() * (len(individual) - 1)) + 1
            individual[swapped], individual[swap_with] = individual[swap_with], individual[swapped]
    return individual
 
# 生成下一代
def next_generation(current_gen, elite_size, mutation_rate):
    ranked_pop = rank_population(current_gen)
    mating_pool = select_mating_pool(current_gen, ranked_pop, elite_size)
    children = []
    length = len(mating_pool) - elite_size
    pool = random.sample(mating_pool, len(mating_pool))
    for i in range(elite_size):
        children.append(mating_pool[i])
    for i in range(length):
        child = breed(pool[i], pool[len(mating_pool)-i-1])
        children.append(child)
    next_gen = [mutate(ind, mutation_rate) for ind in children]
    return next_gen
 
# 遗传算法主函数
def genetic_algorithm(population, pop_size, elite_size, mutation_rate, generations):
    pop = create_initial_population(pop_size, len(population))
    progress = [(0, rank_population(pop)[0][1], pop[0])]  # 记录每代的最短距离和代数
    for i in range(generations):
        pop = next_generation(pop, elite_size, mutation_rate)
        best_route_index = rank_population(pop)[0][0]
        best_distance = rank_population(pop)[0][1]
        progress.append((i + 1, best_distance, pop[best_route_index]))
    best_route_index = rank_population(pop)[0][0]
    best_route = pop[best_route_index]
    return best_route, progress
 
# 调整参数
pop_size = 500       # 增加种群大小
elite_size = 100     # 增加精英比例
mutation_rate = 0.005 # 降低突变率
generations = 20000   # 增加迭代次数
 
# 运行遗传算法
best_route, progress = genetic_algorithm(city_names, pop_size, elite_size, mutation_rate, generations)
 
# 找到最短距离及其对应的代数
min_distance = min(progress, key=lambda x: x[1])
best_generation = min_distance[0]
best_distance = min_distance[1]
 
# 图1：地图上显示城市位置
fig1, ax1 = plt.subplots(figsize=(10, 10))
m1 = Basemap(projection='merc', llcrnrlat=18, urcrnrlat=50, llcrnrlon=80, urcrnrlon=135, resolution='l', ax=ax1)
m1.drawcoastlines()
m1.drawcountries()
m1.fillcontinents(color='lightgray', lake_color='aqua')
m1.drawmapboundary(fill_color='aqua')
for i, (lat, lon) in enumerate(locations):
    x, y = m1(lon, lat)
    m1.plot(x, y, 'bo')
    ax1.text(x, y, str(i), fontsize=8)
ax1.set_title('City Locations')
plt.show()
 
# 图2：适应度随迭代次数变化
fig2, ax2 = plt.subplots(figsize=(10, 5))
ax2.plot([x[1] for x in progress])
ax2.set_ylabel('Distance (km)')
ax2.set_xlabel('Generation')
ax2.set_title('Fitness over Iterations')
# 在图中标注最短距离和对应代数
ax2.annotate(f'Gen: {best_generation}nDist: {best_distance:.2f} km', 
             xy=(best_generation, best_distance), 
             xytext=(best_generation, best_distance + 100),
             arrowprops=dict(facecolor='red', shrink=0.05))
plt.show()
 
# 图3：显示最优路径
fig3, ax3 = plt.subplots(figsize=(10, 10))
m2 = Basemap(projection='merc', llcrnrlat=18, urcrnrlat=50, llcrnrlon=80, urcrnrlon=135, resolution='l', ax=ax3)
m2.drawcoastlines()
m2.drawcountries()
m2.fillcontinents(color='lightgray', lake_color='aqua')
m2.drawmapboundary(fill_color='aqua')
 
# 绘制最优路径和有向箭头
for i in range(len(best_route) - 1):
    x1, y1 = m2(locations[best_route[i]][1], locations[best_route[i]][0])
    x2, y2 = m2(locations[best_route[i + 1]][1], locations[best_route[i + 1]][0])
    m2.plot([x1, x2], [y1, y2], color='g', linewidth=1, marker='o')
 
# 只添加一个代表方向的箭头
mid_index = len(best_route) // 2
mid_x1, mid_y1 = m2(locations[best_route[mid_index]][1], locations[best_route[mid_index]][0])
mid_x2, mid_y2 = m2(locations[best_route[mid_index + 1]][1], locations[best_route[mid_index + 1]][0])
ax3.annotate('', xy=(mid_x2, mid_y2), xytext=(mid_x1, mid_y1), arrowprops=dict(facecolor='blue', shrink=0.05))
 
# 在最优路径图上绘制城市位置
for i, (lat, lon) in enumerate(locations):
    x, y = m2(lon, lat)
    m2.plot(x, y, 'bo')
    ax3.text(x, y, str(i), fontsize=8)
 
# 添加起点和终点标记
start_x, start_y = m2(locations[best_route[0]][1], locations[best_route[0]][0])
end_x, end_y = m2(locations[best_route[-1]][1], locations[best_route[-1]][0])
ax3.plot(start_x, start_y, marker='^', color='red', markersize=15, label='Start (Chongqing)')  # 起点
ax3.plot(end_x, end_y, marker='*', color='blue', markersize=15, label='End')   # 终点
 
# 添加总距离的图例
ax3.legend(title=f'Total Distance: {best_distance:.2f} km')
 
ax3.set_title('Optimal Path')
plt.show()
 

चीनदेशस्य सर्वेषां प्रान्तीयराजधानीनगरानां स्थानदृश्यीकरणं : १.

पुनरावृत्तीनां संख्या २००० (लघुतमं दूरं ३१५९४ किलोमीटर् अस्ति):

ऐतिहासिकपुनरावृत्तिप्रक्रियायां लघुतममार्गस्य पुनरावृत्तिं ज्ञात्वा लघुतममार्गस्य कल्पनां कुर्वन्तु ।

प्रकरणम् २ : पुनरावृत्तीनां संख्या २०,००० (लब्धं लघुतमं दूरं २९,७६८ किलोमीटर्) अस्ति ।

ऐतिहासिकपुनरावृत्तिप्रक्रियायां लघुतममार्गयुक्तं पुनरावृत्तिं ज्ञात्वा तस्य पुनरावृत्तेः लघुतममार्गस्य कल्पनां कुर्वन्तु ।

उपर्युक्ता सामग्री अन्तर्जालतः सारांशतः अस्ति यदि सहायकं भवति तर्हि अग्रिमे समये मिलित्वा अग्रे प्रेषयन्तु।