亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

約束單目標優化

約束單目標優化

Go
神不在的星期二 2021-05-06 17:17:28
介紹我需要使用兩個值集(在這種情況下為重量和體積)將填充有某種類型(例如水桶)的數組拆分,同時將權重的總和保持在最小值(首選)和卷總數之間的差異小于1000(必需)。這不必是一個完整的遺傳算法或類似的東西,但是它應該比我目前擁有的更好。當前實施由于不知道如何做得更好,因此我首先將數組拆分為兩個相同長度的數組(該數組可以填充數量不等的項目),然后用兩個值均為0的項目替換可能存在的空白點。雙方不必擁有相同數量的物品,否則我只是不知道該如何處理。在分發完這些之后,我正在嘗試像這樣優化它們:func (main *Main) Optimize() {    for {        difference := main.Difference(WEIGHT)        for i := 0; i < len(main.left); i++ {            for j := 0; j < len(main.right); j++ {                if main.DifferenceAfter(i, j, WEIGHT) < main.Difference(WEIGHT) {                    main.left[i], main.right[j] = main.right[j], main.left[i]                }            }        }        if difference == main.Difference(WEIGHT) {            break        }    }    for main.Difference(CAPACITY) > 1000 {        leftIndex := 0        rightIndex := 0        liters := 0        weight := 100        for i := 0; i < len(main.left); i++ {            for j := 0; j < len(main.right); j++ {                if main.DifferenceAfter(i, j, CAPACITY) < main.Difference(CAPACITY) {                    newLiters := main.Difference(CAPACITY) - main.DifferenceAfter(i, j, CAPACITY)                    newWeight := main.Difference(WEIGHT) - main.DifferenceAfter(i, j, WEIGHT)                    if newLiters > liters && newWeight <= weight || newLiters == liters && newWeight < weight {                        leftIndex = i                        rightIndex = j                        liters = newLiters                        weight = newWeight                    }                }            }        }        main.left[leftIndex], main.right[rightIndex] = main.right[rightIndex], main.left[leftIndex]    }}職能:main.Difference(const)計算兩側的絕對差,作為參數的常數決定用于計算差的值main.DifferenceAfter(i,j,const)模擬兩個存儲桶之間的交換,i是左側的存儲桶,j是右側的存儲桶,并計算所得的絕對差,然后,該常數再次確定要檢查的值結論我想我需要在這里包括更多的數學信息,但是老實說,我一直呆在這里,不知道如何繼續在這里,所以我想從您那里得到一些幫助,基本上可以在這里為我提供幫助。
查看完整描述

2 回答

?
人到中年有點甜

TA貢獻1895條經驗 獲得超7個贊

如前所述,您的問題實際上是一個受約束的優化問題,對您的數量差異有約束。


在數學上,這將在體積差異小于1000的約束下最小化體積差異。將其表示為線性優化問題的最簡單方法是:


min weights . x

    subject to  volumes . x < 1000.0

                for all i, x[i] = +1 or -1

a . b矢量點積在哪里。解決此問題后,所有索引x = +1對應于您的第一個數組,所有索引x = -1對應于您的第二個數組。


不幸的是,已知0-1整數編程是NP-hard的。解決該問題的最簡單方法是對空間進行窮盡的蠻力探索,但它需要測試所有2^n可能的向量x(n原始weights和volumes向量的長度在哪里),這些向量可能會很快失去控制。關于此主題的文獻很多,算法更為有效,但它們通常針對特定的問題和/或約束條件。您可以在Google上搜索“線性整數編程”,以查看在此主題上所做的事情。


我認為最簡單的方法可能是執行基于啟發式的蠻力搜索,在這種情況下,您會盡早修剪搜索樹,以免超出體積約束,并保持接近約束(一般而言,線性解優化問題在可行空間的邊緣)。

如果您一般不熟悉優化文章或數學知識,那么Wikipedia文章會提供很好的介紹,但是有關此主題的大多數文章會迅速顯示一些您可以立即適應的(偽)代碼。

如果您n的解決方案很大,我認為您將不得不在解決方案的優化程度與計算速度之間做出權衡。您的解決方案可能不是最佳選擇,但是它比窮舉搜索要快得多。可能會有更好的權衡取舍,具體取決于問題的確切配置。


查看完整回答
反對 回復 2021-05-17
  • 2 回答
  • 0 關注
  • 307 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號